B - Flipping Cards Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君はテーブルの上に N 枚のカードを並べました。各カードには表面と裏面があり、それぞれに整数が書かれています。 i 番目のカードの表面には整数 F_i が、裏面には整数 B_i が書かれています。最初、すべてのカードは表面が上を向いた状態で置かれています。

高橋君は、これらの N 枚のカードの中から異なる K 枚を選んで裏返す（裏面が上を向くようにする）ことができます。裏返さなかった残りのカードは表面が上を向いたままです。

すべてのカードの上を向いている面に書かれた整数の合計値を最大化するとき、その最大値を求めてください。

制約

  • 1 \leq N \leq 20
  • 0 \leq K \leq N
  • 1 \leq F_i \leq 100
  • 1 \leq B_i \leq 100
  • 入力はすべて整数である

入力

N K
F_1 B_1
F_2 B_2
\vdots
F_N B_N
  • 1 行目には、カードの枚数を表す整数 N と、裏返すカードの枚数を表す整数 K が、スペース区切りで与えられる。
  • i + 1 行目 (1 \leq i \leq N) には、 i 番目のカードの表面の値 F_i と裏面の値 B_i が、スペース区切りで与えられる。

出力

高橋君がちょうど K 枚のカードを裏返したときの、上を向いている面に書かれた整数の合計値の最大値を 1 行で出力してください。

入力例 1

3 1
1 5
3 2
4 1

出力例 1

12

入力例 2

3 0
2 5
3 1
4 3

出力例 2

9

入力例 3

8 3
10 20
15 5
8 12
6 6
20 25
3 1
7 18
9 4

出力例 3

104

入力例 4

15 5
12 30
25 10
8 15
50 45
33 40
19 2
7 55
44 44
16 28
5 90
61 20
38 42
14 9
27 35
10 10

出力例 4

540

入力例 5

1 1
3 7

出力例 5

7

Score : 300 pts

Problem Statement

Takahashi has placed N cards on a table. Each card has a front side and a back side, each with an integer written on it. The front side of the i-th card has the integer F_i, and the back side has the integer B_i. Initially, all cards are placed with their front side facing up.

Takahashi can choose exactly K distinct cards from these N cards and flip them over (so that their back side faces up). The remaining cards that are not flipped stay with their front side facing up.

Find the maximum possible value of the sum of the integers written on the face-up sides of all the cards.

Constraints

  • 1 \leq N \leq 20
  • 0 \leq K \leq N
  • 1 \leq F_i \leq 100
  • 1 \leq B_i \leq 100
  • All input values are integers

Input

N K
F_1 B_1
F_2 B_2
\vdots
F_N B_N
  • The first line contains the integer N representing the number of cards and the integer K representing the number of cards to flip, separated by a space.
  • The (i + 1)-th line (1 \leq i \leq N) contains the front side value F_i and the back side value B_i of the i-th card, separated by a space.

Output

Print on a single line the maximum possible sum of the integers written on the face-up sides when Takahashi flips exactly K cards.

Sample Input 1

3 1
1 5
3 2
4 1

Sample Output 1

12

Sample Input 2

3 0
2 5
3 1
4 3

Sample Output 2

9

Sample Input 3

8 3
10 20
15 5
8 12
6 6
20 25
3 1
7 18
9 4

Sample Output 3

104

Sample Input 4

15 5
12 30
25 10
8 15
50 45
33 40
19 2
7 55
44 44
16 28
5 90
61 20
38 42
14 9
27 35
10 10

Sample Output 4

540

Sample Input 5

1 1
3 7

Sample Output 5

7