区间翻转(Range Flip)

题目描述

有 $N$ 张卡片排成一排，卡片 $i$ 的正面写有 $A_i$，背面写有 $B_i$。初始时所有卡片正面朝上。

你可以执行以下操作最多 $K$ 次：

选择整数 $l, r$（$1 \leq l \leq r \leq N$），将区间 $[l, r]$ 内的所有卡片翻面。翻面后，正面朝上的变为背面朝上，背面朝上的变为正面朝上。

求操作后朝上面的数字之和的最大值。

输入格式

输入从标准输入按以下格式给出：

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

• 第 1 次操作选择 $l=2, r=5$，翻面后朝上面为 $2, 9, 5, 2, 8, 7, 5$
• 第 2 次操作选择 $l=4, r=4$，翻面后朝上面为 $2, 9, 5, 9, 8, 7, 5$
• 和为 $2+9+5+9+8+7+5=45$

样例输入 #2

5 6
9 6
3 2
8 1
7 5
8 4

样例输出 #2

35

可以不执行任何操作，此时和为 $9+3+8+7+8=35$。

样例输入 #3

9 1
2 7
9 4
1 1
6 1
3 4
8 9
1 2
7 5
3 9

样例输出 #3

47

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10$
• $1 \leq A_i, B_i \leq 10^9$
• 所有输入值为整数

知识点与难度

本题涉及的知识点从属于 GESP 四级，难度等级：⭐⭐⭐。

测试点分布