文件读写

输入文件：flip.in

输出文件：flip.out

题目描述

有 $N$ 张卡片排成一行，编号为 $1,2,\ldots,N$。第 $i$ 张卡片的正面写着整数 $A_i$，反面写着整数 $B_i$。初始时所有卡片都是正面朝上。

你最多可以进行 $K$ 次操作。每次选择一段连续区间 $[l,r]$（$1\le l\le r\le N$），将区间内所有卡片翻面。各次操作选择的区间可以重叠，同一张卡片每次被操作都会翻面。

求操作结束后，所有卡片朝上一面的数字之和的最大值。可以一次操作也不进行。

输入格式

第一行两个整数 $N,K$。

接下来 $N$ 行，每行两个整数 $A_i,B_i$。

输出格式

输出一个整数，表示数字之和的最大值。

样例 1

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

45

先翻转区间 $[2,5]$，再翻转区间 $[4,4]$，朝上的数字依次为 $2,9,5,9,8,7,5$，总和为 $45$。

样例 2

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

35

样例 3

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

47

数据范围

对于所有测试数据，$1\le N\le2\times10^5$，$1\le K\le10$，$1\le A_i,B_i\le10^9$。所有输入值均为整数。

本题选自玄武 OJ abc466e — Range Flip。