E - Range Flip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

N 枚のカードが並んでいます。カードには 1, 2, \ldots, N の番号が付けられています。

カード i の表面には整数 A_i が、裏面には整数 B_i が書かれています。はじめ、すべてのカードは表面が上を向いています。

あなたは、以下の操作を高々 K 回行うことができます。

  • 1 \leq l \leq r \leq N なる整数 l, r を選ぶ。l \leq i \leq r なる各整数 i について、カード 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

1 回目の操作で l = 2, r = 5 とし、2 回目の操作で 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

1 回も操作を行わなくてもよいです。

入力例 3

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

出力例 3

47

Score : 450 points

Problem Statement

There are N cards lined up. The cards are numbered 1, 2, \ldots, N.

On the front side of card i, an integer A_i is written, and on the back side, an integer B_i is written. Initially, every card is facing front side up.

You can perform the following operation at most K times.

  • Choose integers l and r satisfying 1 \leq l \leq r \leq N. For each integer i satisfying l \leq i \leq r, flip card i. Here, flipping a card means turning the side that was facing down before the operation to face up.

After finishing the operations, find the maximum possible value of the sum of the numbers written on the side of the cards that is facing up.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10
  • 1 \leq A_i, B_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer.

Sample Input 1

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

Sample Output 1

45

If you choose l = 2, r = 5 in the first operation and l = 4, r = 4 in the second operation, the numbers written on the side facing up, in order of the card numbers, become 2, 9, 5, 9, 8, 7, 5, and their sum is 45.

Sample Input 2

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

Sample Output 2

35

It is fine if you perform no operation.

Sample Input 3

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

Sample Output 3

47