← 返回题目列表

AtCoder · abc466_e

E. 范围翻转

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

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