问题描述

高桥被指派了一个任务，要将屏幕截图粘贴到电子表格软件中作为软件正常运行的证据。屏幕截图一共有 $N$ 张，它们的高度都相同，但宽度不同。另外，对于可以粘贴到电子表格软件中的屏幕截图，有两个限制条件：

1. 电子表格软件的宽度只有 $W$。因此，粘贴的屏幕截图的宽度总和必须小于等于 $W$。
2. 电子表格软件无法粘贴超过 $K$ 张屏幕截图。因此，可以粘贴到电子表格软件中的屏幕截图最多只能有 $K$ 张。

此外，屏幕截图还有一个"重要度"的属性。高桥希望在满足上述两个限制条件的同时，使得粘贴的屏幕截图的重要度总和最大化。然而，这个任务对他来说很困难，所以请你帮他计算可以粘贴到电子表格软件中的屏幕截图的重要度总和的最大值。

输入

从标准输入中按以下格式给出输入。

$W$ $N$ $K$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$

• 第 $1$ 行为电子表格软件的宽度 $W (1 \le W \le 10000)$。
• 第 $2$ 行为屏幕截图的数量 $N (1 \le N \le 50)$ 和可以粘贴到电子表格软件中的屏幕截图的张数 $K(1 \le K \le N)$，两个数以空格分隔。
• 第 $3$ 行到第 $N$ 行描述了每张屏幕截图的信息。其中第 $i$ 行描述了第 $i$ 张屏幕截图的宽度 $A_i (1 \le A_i \le 1000)$ 和重要度 $B_i (1 \le B_i \le 100)$，两个数以空格分隔。

输出

输出粘贴到电子表格软件中的屏幕截图的重要度总和的最大值，输出占一行。末尾必须换行。

输入示例1

10
3 2
4 20
3 40
6 100

输出示例1

140

选择第 $2$ 和第 $3$ 张屏幕截图，它们的总宽度为 $9$，使用的屏幕截图数量为 $2$，符合条件。此时重要度的和为 $40 + 100 = 140$。

输入示例2

10
5 4
9 10
3 7
3 1
2 6
4 5

输出示例2

18

请注意，不一定需要使用 $K$ 张屏幕截图。

输入示例3

22
5 3
5 40
8 50
3 60
4 70
6 80

输出示例3

210

请注意，即使宽度足够，也只能放置最多 $K$ 张屏幕截图。