#P7222. C. 礼盒

C. 礼盒

C. 礼盒

题目描述

nn组礼盒,每组有一个红礼盒和一个蓝礼盒,里面分别有价值aia_ibib_i的礼品。现在你想选xx个红礼盒和nxn - x个蓝礼盒,每组里面只能恰好选一个。问你能获得的最大价值是多少

输入格式

第一行输入两个整数n,xn, x

接下来nn行,每行输入两个整数ai,bia_i, b_i

输出格式

输出一个数表示答案

输入样例1

4 2
1 2
3 2
4 1
1 4

输出样例1

13

数据范围

对于30%的数据,n20n \leq 20

对于60%的数据,n2000n \leq 2000

对于100%的数据,$n \leq 2 \times 10^5, 0 \leq x \leq n, 1 \leq a_i, b_i \leq 10^9$