时空限制

1S/512M

题目描述

jiangly 计划在接下来的 $n$ 天刷题。

第 $i$ 天可以进行下面三种操作之一：

1. 玩游戏，收益为 $0$。
2. 刷一道套路题，收益为 $a_i$。
3. 刷一道思维题，收益为 $b_i$。

但由于某些原因，jiangly 必须遵守下面三条原则：

1. 必须恰好玩 $m$ 天游戏。
2. 不能连续玩两天游戏。
3. 相邻两道题目的专题不同。这里的相邻两道题目不要求在相邻两天。比如不能在第 $1$ 天和第 $3$ 天刷套路题并在第 $2$ 天玩游戏。

你需要回答 jiangly 能获得的最大收益。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示 jiangly 的计划天数和 jiangly 的玩游戏天数。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$，分别表示 jiangly 第 $i$ 天刷套路题和刷思维题的收益。

输出格式

一行一个整数，表示 jiangly 能获得的最大收益。

样例

样例输入 #1

6 2
8 1
3 9
10 2
7 11
9 3
4 12

样例输出 #1

39

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le m \le \lceil \dfrac{n}{2} \rceil$，$1 \le a_i, b_i \le 10^9$。