Sleep Gardening

Amelia is having a very strange dream. For some reason she has been placed in charge of a garden. This garden is laid out in a long row and consists of $N$ segments numbered from $1$ to $N$. In this garden there are initially $M$ trees, the $i$-th of which is $h_i$ metres tall and is located in segment $p_i$.

Amelia has been tasked with improving the garden by increasing the amount of foliage. The way that she can do this is also somewhat strange: up to $K$ times she can select a contiguous range of segments and remove all trees in those spots, and plant a sapling with a height of 1 metre in every segment within the range.

Amelia is of course asleep (and so has some difficulty programming) so she has asked for your help to write a program to determine the maximum possible sum of the heights of all the trees in the garden after performing this action up to $K$ times.

Input

The first line contains three integers $N, M, K$ separated by spaces.

The following $M$ lines each contain two integers $p_i$ and $h_i$ separated by a space, which are the position and height of the $i$-th tree respectively.

Output

Output a single line, the maximum sum of all tree heights in the garden that you can achieve.

Constraints

• $1 \le M, K \le 100,000$
• $M \le N \le 10^9$
• $2 \le h_i \le 10^9$ and $1 \le p_i \le N$ for $1 \le i \le M$
• The positions of all trees are unique and the trees are listed in increasing order of position

Subtasks

• Subtask 1 (10%): $K = 1$ and $M = 1$
• Subtask 2 (11%): $K = 1$ and $N \le 100$
• Subtask 3 (23%): $K = 1$
• Subtask 4 (44%): $K \le 50$
• Subtask 5 (12%): No further constraints.

Notes

If you are using a type sensitive language like C++, Java, or C then make sure to use a 64 bit integer type to avoid integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

If you are using Python and your solution is exceeding the time limit, try selecting Python 3.11 (PyPy 7.3.19) when submitting as this will generally make your code run faster.

Sample Explanations

Sample 1

In this sample the garden is $8$ segments long and there is a single tree in segment $3$ with height $4$. Amelia can perform the planting operation either zero or one time. It is optimal for Amelia to plant saplings in segments $4$ through $8$ in one operation. This brings the total sum of the heights of all trees up to $4 + 1 \times 5 = 9$.

Sample 2

It is optimal for Amelia to clear segments $6$ through $10$ and replace them with saplings. This brings the total height of all trees up to $7 + 4 + 1 \times 5 = 16$.

Sample 3

It is optimal for Amelia to replace segments $4$ to $6$ and segments $8$ to $11$ with saplings. This increases the total amount of foliage to $19$.