该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

C. 礼盒

题目描述

有$n$组礼盒，每组有一个红礼盒和一个蓝礼盒，里面分别有价值$a_i$和$b_i$的礼品。现在你想选$x$个红礼盒和$n - x$个蓝礼盒，每组里面只能恰好选一个。问你能获得的最大价值是多少

输入格式

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

接下来$n$行，每行输入两个整数$a_i, b_i$

输出格式

输出一个数表示答案

输入样例1

4 2
1 2
3 2
4 1
1 4

输出样例1

13

数据范围

对于30%的数据，$n \leq 20$

对于60%的数据，$n \leq 2000$

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