该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小Z上初一了！终于学习到了一次函数：$f(x)=kx+b$。

他一次性自创了好几个一次函数: $f_1(x)=k_1x+b_1,f_2(x)=k_2x+b_2,...f_n(x)=k_nx+b_n$，他想从中选出 $m$ 个，进行函数套娃：

$$f_{tm}...​​(f_{t3}​​(f_{t2}​​(f_{t1}​​(1)...)))$$

其中$1\leq t_{1,2,3...m}\leq n$ 同时互不相同

他想知道能得到的最大结果是多少

输入格式

第一行两个正整数分别表示$n,m$。

接下来一共 $n$ 行,第 $i$ 行表示第 $i$ 个一次函数的 $k_i$ 和 $b_i$。

输出格式

一个整数结果，表示最后套娃能得到的最大值

输入输出样例

2 2 
2 2 
2 3

12

样例 $\tt \#1$说明

先进行 $f(x)=2x+3=5$

再进行 $f(x)=2x+2=12$

3 2
1 2 
3 4
5 6

41

样例 $\tt \#2$说明

先进行 $f(x)=3x+4=7$

再进行 $f(x)=5x+6=41$

10 9
49 43
50 37
38 43
11 22
50 46
4 48
22 50
47 40
6 5
39 9

112264948867002

数据范围

$30\%:$ 保证$1 \leq n \leq 10$。

另外$10\%:$ 保证所有 $k$ 都相同。

另外$10\%:$ 保证所有 $b$ 都相同。

$100\%:$ 保证 $1\leq n\leq 2*10^5$,$1\leq m \leq min(n,10)$,$1\leq k_i,b_i \leq 50$。
$k$ 和 $b$ 都为整数