/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
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 )) としてありえる最大値を求めてください。
制約
- 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)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを整数として出力せよ。
入力例 1
3 2 2 3 1 5 4 2
出力例 1
26
ありえるすべての 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 と出力します。
入力例 2
10 3 48 40 34 22 24 37 45 40 48 31 49 44 45 40 44 6 35 22 39 28
出力例 2
216223
Score : 500 points
Problem Statement
You are given N linear functions f_1, f_2, \ldots, f_N, where f_i(x) = A_i x + B_i.
Find the maximum possible value of f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots )) for a sequence p = (p_1, p_2, \ldots, p_K) of K distinct integers between 1 and N, inclusive.
Constraints
- 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)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer as an integer.
Sample Input 1
3 2 2 3 1 5 4 2
Sample Output 1
26
Here are all possible p and the corresponding values of 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
Therefore, print 26.
Sample Input 2
10 3 48 40 34 22 24 37 45 40 48 31 49 44 45 40 44 6 35 22 39 28
Sample Output 2
216223