Problem Description

Takahashi has been tasked with pasting screenshots of the screen into a spreadsheet software as evidence that the software is working as expected. There are $ N $ screenshots, all of which have the same height but different widths. Additionally, there are two constraints for pasting screenshots into the spreadsheet software:

1. The spreadsheet software has a width of $ W $. Therefore, the total width of the pasted screenshots must not exceed $ W $.
2. The spreadsheet software cannot paste more than $ K $ screenshots. Hence, only up to $ K $ screenshots can be pasted.

Furthermore, each screenshot has an "importance" value. Takahashi wants to maximize the total importance of the pasted screenshots while satisfying the two constraints. Since this task is difficult for him, you are asked to find the maximum total importance of the screenshots that can be pasted into the spreadsheet software on his behalf.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains the width of the spreadsheet software $W\ (1\ ≦\ W\ ≦\ 10000)$.
• The second line contains the number of screenshots $N\ (1≦N≦50)$ and the maximum number of screenshots that can be pasted $ K(1≦K≦N) $, separated by spaces.
• The next $ N $ lines provide information about each screenshot. The $ i $ -th line contains the width $A_i\ (1\ ≦\ A_i\ ≦\ 1000)$ and the importance $B_i\ (1\ ≦\ B_i\ ≦\ 100)$ of the $ i $ -th screenshot, separated by spaces.

Output Format

Output the maximum total importance of the screenshots that can be pasted into the spreadsheet software in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

10
3 2
4 20
3 40
6 100

Sample Output #1

140

Sample Input #2

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

Sample Output #2

18

Sample Input #3

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

Sample Output #3

210

Notes/Hints

Sample Explanation 1

Choosing the 2nd and 3rd screenshots results in a total width of $ 9 $ and uses $ 2 $ screenshots, satisfying the conditions. The sum of their importance values is $40\ +\ 100$ , which equals $ 140 $.

Sample Explanation 2

Note that you do not necessarily have to use $ K $ screenshots.

Sample Explanation 3

Even if the width is sufficient, note that you can only place up to $ K $ screenshots at most.

见题面 Input 部分

见题面 Output 部分