← 返回题目列表

AtCoder · awc0073_b

B. 翻转卡片

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

分数: 300 分

问题陈述

高桥已放置 N 桌子上的卡片。每张卡片都有正面和背面,每面都写有一个整数。正面 i第一张卡有整数 F_i,背面有整数 B_i。最初,所有卡片的正面朝上放置。

高桥可以准确选择 K 不同 上面写着 这些卡片 N 卡并将其翻转(使其背面朝上)。其余未翻转的卡片正面朝上。

找出所有卡片正面朝上的整数之和的最大可能值。

约束

  • 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
  • 第一行包含整数 N 代表卡片数量和整数 K 代表要翻转的卡片数量,以空格分隔。
  • 的 (i + 1)第行 (1 \leq i \leq N) 包含正面值 F_i 和背面值 B_i 的 i第一张卡,以空格分隔。

输出

在单行上打印当高桥完全翻转时写在面朝上的整数的最大可能总和 K 卡。


示例输入 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