分数: 450 点
问题陈述
有 N 卡片排列整齐。卡片已编号 1, 2, \ldots, N.
在卡的正面 i,一个整数 写着 A_i ,背面写着一个整数 写入 B_i 。最初,每张卡片正面朝上。
您最多可以执行以下操作 K 次。
- 选择整数 l 和 r 满意 1 \leq l \leq r \leq N。对于每个整数 i 满意 l \leq i \leq r, 翻页卡 i。这里,翻牌是指将操作前朝下的一面翻到朝上。
完成运算后,求卡片正面朝上的数字之和的最大可能值。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10
- 1 \leq A_i, B_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
输出答案。
示例输入 1
7 2 2 1 6 9 3 5 9 2 4 8 7 4 5 6
示例输出 1
45
如果您选择 l = 2, r = 5 在第一次操作中并且 l = 4, r = 4 在第二次操作中,正面朝上写的数字,按照卡号的顺序,变成 2, 9, 5, 9, 8, 7, 5,它们的总和是 45.
示例输入 2
5 6 9 6 3 2 8 1 7 5 8 4
示例输出 2
35
不进行任何操作也可以。
示例输入 3
9 1 2 7 9 4 1 1 6 1 3 4 8 9 1 2 7 5 3 9
示例输出 3
47