← 返回题目列表

AtCoder · abc366_f

I. 最大构图

中文机器翻译题面 查看原题

分数: 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