分数: 500 点
问题陈述
你被给予 N 线性函数 f_1, f_2, \ldots, f_N,其中 f_i(x) = A_i x + B_i.
找到最大可能值 f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots )) 序列 p = (p_1, p_2, \ldots, p_K) of K 不同 之间的整数 1 和 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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