A94841.复合函数最大值

给定 $N$ 个一次函数 $f_1, f_2, \ldots, f_N$，其中第 $i$ 个函数的表达式为 $f_i(x) = A_i x + B_i$。

你需要从这 $N$ 个函数中选出 $K$ 个不同的函数，并决定它们的排列顺序。设选出的函数下标依次为 $p_1, p_2, \ldots, p_K$（其中 $p_i$ 互不相同），请计算复合函数 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1)\ldots ))$ 能取得的最大值。

第一行包含两个整数 $N$ 和 $K$。

接下来 $N$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示第 $i$ 个函数的系数。

输出一个整数，表示能取得的最大值。

样例解释 1

对于所有可能的排列 $p$ 及其对应的 $f_{p_1}(f_{p_2}(1))$ 的值如下：

• $p = (1, 2)$：$f_1(f_2(1)) = 2(1(1)+5)+3 = 15$
• $p = (1, 3)$：$f_1(f_3(1)) = 2(4(1)+2)+3 = 15$
• $p = (2, 1)$：$f_2(f_1(1)) = 1(2(1)+3)+5 = 10$
• $p = (2, 3)$：$f_2(f_3(1)) = 1(4(1)+2)+5 = 11$
• $p = (3, 1)$：$f_3(f_1(1)) = 4(2(1)+3)+2 = 22$
• $p = (3, 2)$：$f_3(f_2(1)) = 4(1(1)+5)+2 = 26$

最大值为 $26$。

数据范围

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq K \leq \min(N, 10)$
• $1 \leq A_i, B_i \leq 50$
• 输入均为整数。