分数: 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