题目描述

小明在研究一个含有绝对值的函数

$f(x)=c_1|a_1x+b_1|+c_2|a_2x+b_2|+\cdots+c_n|a_nx+b_n|$

其中 $c_i|a_i x+b_i|$ 表示 $a_i\times x+b_i$ 的绝对值乘以 $c_i$。

小明打算计算出 $x=0,1,\cdots ,M$ 时 f(x) 的值，然后找出这 M+1 个值中的最大值和最小值。

但是计算所有 f(x) 的值的工作量太大，所以他打算把任务交给你，你只需要找出这些值中的最大值和最小值即可。

输入格式

第1行，2个正整数 n,M。

接下来 n 行，每行三个整数 $a_i$,$b_i$,$c_i$。

输出格式

输出两个整数，表示当 $x=0,1,\cdots ,M$时，M+1 个 f(x) 的值中的最大值和最小值。 用空格分隔。

样例输入

样例输入 1

3 5
1 3 1
1 -4 -4
-2 5 1

样例输入 2

4 10
-1 -4 0
0 5 4
1 0 -5
2 -4 -3

样例输入 3

8 100000000
-279 -718 -374
827 868 310
-314 771 -997
-200 890 646
729 -848 636
3 18 347
-627 152 261
20 417 -426

样例输出

样例输出 1

10 -8

样例输出 2

10 -78

样例输出 3

58797799443899 163467

提示

样例1说明：

函数$f(x)=|x+3|-4|x-4|+|-2x+5|$，依次将$x=0,1,2,3,4,5$代入计算可得：

$f(0)=-8$，$f(1)=-5$，$f(2)=-2$，$f(3)=3$，$f(4)=10$，$f(5)=9$。

最大值是10，最小值是−8。

对于 50% 的数据：$M\le 1000$。

对于 100% 的数据：$1\le n\le 3000$；$1\le M\le 10^{9}$；

$-1000\le a_i\le 1000$；$-10^{9}\le b_i\le 10^{9}$；$-1000\le c_i\le 1000$。

4 10
-1 -4 0
0 5 4
1 0 -5
2 -4 -3

10 -78

5 5
1 1 -2
-1 2 1
-2 4 4
-1 -5 2
-2 2 5

75 17

4 10  
-1 -4 0  
0 5 4  
1 0 -5  
2 -4 -3

10 -78