题目描述

小核桃有 $n$ 个一次函数 $f_i(x)=k_i x+b_i$。他想挑出 $m$ 个互不相同的函数，并决定它们的代入顺序。

初始值 $x=1$，每代入一个函数，$x$ 就更新为这个函数在此刻的值。请你求出依次代入这 $m$ 个函数后，$x$ 能取到的最大值。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，第 $i$ 行两个整数 $k_i,b_i$，表示第 $i$ 个一次函数。

输出格式

一行，一个整数，表示最终 $x$ 的最大值。

样例

2 2
2 3
2 2

12

3 2
1 2
3 4
5 6

41

4 3
1 10
2 1
3 5
4 2

154

样例解释

样例 1 中，先代入 $f(x)=2x+3$，$x$ 由 $1$ 变为 $5$；再代入 $f(x)=2x+2$，$x$ 由 $5$ 变为 $12$。

样例 2 中，选 $f(x)=3x+4$ 与 $f(x)=5x+6$，先代入前者得 $7$，再代入后者得 $41$。

样例 3 中，选 $f(x)=x+10$、$f(x)=3x+5$、$f(x)=4x+2$，依次代入得 $1\to 11\to 38\to 154$。

数据范围与约定

对于 $100\%$ 的数据，$1\le n\le 2\times10^5$，$1\le m\le \min(n,10)$，$1\le k_i,b_i\le 50$。