小Z接到一项工作：把屏幕截图粘贴进电子表格里，作为「软件按预期运行」的证据。

他手上有 N 张截图，**高度都相同**，但**宽度各不相同**。往表格里贴图有两个限制：

1. 表格的宽度只有 W，因此贴进去的截图**宽度之和不能超过 W**；

2. 表格最多只能贴 K 张截图。

每张截图还有一个**重要度**。小Z希望在满足上面两个限制的前提下，让贴进去的截图**重要度之和最大**。

请你求出这个最大重要度之和。

第一行一个整数 W（1 \leq W \leq 10000），表示表格的宽度。

第二行两个整数 N,K（1 \leq N \leq 50，1 \leq K \leq N），分别表示截图的数量与最多可贴的张数。

接下来 N 行，第 i 行两个整数 A_i,B_i（1 \leq A_i \leq 1000，1 \leq B_i \leq 100），分别表示第 i 张截图的宽度与重要度。

输出能满足条件的截图重要度之和的最大值，一行一个整数。

**样例1说明**：选第 2、3 张：宽度和 3+6=9\le 10，张数 2\le K，重要度 40+100=140。

- 1\le W\le 10000；

- 1\le N\le 50，1\le K\le N；

- 1\le A_i\le 1000，1\le B_i\le 100；

 20% | 1~5 | 20 | N \le 18 | 

| 60% | 6~15 | 40 | N \le 22，W \le 500 | 

| 100% | 16~25 | 40 | N,K\le 50，W\le 10000 |