Course Registration

Time limit2sMemory limit256 MB

Summary

Choose courses so total credits fall between n_lo and n_hi, maximizing the sum of their happiness scores, with each course credit at most 5.

Level: Medium6 of 10
Topics: Greedy, Sorting, Dynamic programming
Solved: No attempts yet

Problem

This semester, GIST offers $m$ courses in total. Cheongeung wants to take at least $n\_\text{lo}$ credits and at most $n\_\text{hi}$ credits. After looking through the course list, Cheongeung gave every course a happiness score. The happiness for the semester is the sum of the happiness scores of all courses taken. Timetable conflicts do not need to be considered. Write a program that finds the maximum happiness Cheongeung can get this semester.

Input

The first line contains $n\_\text{lo}$ and $n\_\text{hi}$ , the minimum and maximum credits, separated by a space. They satisfy $0\leq n\_\text{lo}\leq n\_\text{hi}\leq 200,000$ .

The second line contains $m$ , the number of courses offered this semester. It satisfies $1\leq m\leq 200,000$ .

Each of the next $m$ lines contains the credit $g_i$ and the happiness $s_i$ of course $i$ , separated by a space. They satisfy $0\leq g_i\leq 5$ and $-100\leq s_i\leq 100$ . The input always contains at least one combination of courses that meets the credit requirement.

Output

Print the maximum happiness Cheongeung can get this semester.

Examples2

Example 1
Input
```
2 2
4
0 2
1 1
1 3
1 -1
```
Expected output
```
6
```

Example 2

Input

Expected output