AT_abc366_f [ABC366F] Maximum Composition

[problemUrl]: https://atcoder.jp/contests/abc366/tasks/abc366_f $ N $ 個の一次関数 $ f_1,f_2,\ldots,f_N $ が与えられます。$ f_i(x)=A_i\ x+B_i $ です。 $ 1 $ 以上 $ N $ 以下の**相異なる** $ K $ 個の整数からなる長さ $ K $ の数列 $ p=(p_1,p_2,\ \ldots\ p_K) $ について、$ f_{p_1}(f_{p_2}(\ldots\ f_{p_K}(1)\ldots\ )) $ としてありえる最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_N $ $ B_N $

答えを整数として出力せよ。

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^{5} $ - $ 1\ \leq\ K\ \leq\ \text{min}(N,10) $ - $ 1\ \leq\ A_i,B_i\ \leq\ 50 $ $ (1\ \leq\ i\ \leq\ N) $ - 入力はすべて整数 ### Sample Explanation 1 ありえるすべての $ p $ とそれに対応する $ f_{p_1}(f_{p_2}(1)) $ の値は以下の通りです。 - $ p=\ (\ 1,2\ ) $ : $ f_1(f_2(1))=15 $ - $ p=\ (\ 1,3\ ) $ : $ f_1(f_3(1))=15 $ - $ p=\ (\ 2,1\ ) $ : $ f_2(f_1(1))=10 $ - $ p=\ (\ 2,3\ ) $ : $ f_2(f_3(1))=11 $ - $ p=\ (\ 3,1\ ) $ : $ f_3(f_1(1))=22 $ - $ p=\ (\ 3,2\ ) $ : $ f_3(f_2(1))=26 $ よって、 $ 26 $ と出力します。