题目描述

在一条东西方向的道路有 $n$ 个坑，从西到东编号从 $1$ 到 $n$。每个坑可以不种树，也可以种一棵树。但是每个坑最多只能种一棵树。

有 $m_1 + m_2$ 个限制。

前 $m_1$ 个限制的第 $i$ 个限制表示为三个整数 $l_i, r_i, c_i$，它表示：区间 $[l_i, r_i]$ 范围内最多种 $c_i$ 棵树。

后 $m_2$ 个限制的第 $i$ 个限制表示为三个整数 $l_i, r_i, c_i$，它表示：区间 $[l_i, r_i]$ 范围内至少种 $c_i$ 棵树。

问：满足所有限制的情况下最多种多少棵树，最少种多少棵树？

输入格式

第一行，三个整数 $n, m_1, m_2(1 \le n, m_1, m_2 \le 1000)$，以空格分隔。

接下来 $m_1 + m_2$ 行，每行包含三个整数 $l_i, r_i, c_i$，以空格分隔（$1 \le l_i \le r_i \le n, 0 \le c_i \le r_i - l_i + 1$）。

输出格式

如果不存在任何满足所有限制条件的种树方案，输出一行 so sad!。

否则，输出一行，包含两个整数，以空格分隔，分别表示满足所有限制的情况下最多种多少棵树，以及最少种多少棵树。

样例

10 1 1
1 8 5
7 10 2

7 2

10 2 1
1 5 2
6 10 2
3 8 5

so sad!

说明/提示

同类题目练习：

• atcoer abg216 G - 01Sequence