caffeinate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Johnny is a busy man – he has many events scheduled on his calendar. As Johnny has some school assignments that he hasn't completed yet, he wants to keep Claude Code running on his computer for as long as possible, but whenever he is away at an event, his computer shuts down immediately by default to save power. Fortunately, Johnny can use the command line utility caffeinate to keep his computer running. In particular, if Johnny uses the command caffeinate, his computer will stay on for $$$T$$$ minutes, regardless of whether or not Johnny uses his computer in that time window.

Johnny can use the caffeinate command up to $$$k$$$ times at any moment he chooses (even if he is away at an event). Given $$$n$$$ events on Johnny's calendar, Johnny wants to know – what is the maximum amount of time Johnny can run Claude Code for when he is away at events?

Input

The first line contains three space-separated integers $$$n$$$, $$$k$$$, $$$T$$$ ($$$1 \le n, k \le 100$$$, $$$1 \le T \le 10^9$$$) — the number of events Johnny has, the maximum allowed number of caffeinate usages, and the time in minutes that caffeinate keeps Johnny's computer on, respectively.

The next $$$n$$$ lines contain two integers each, where the $$$i$$$-th line contains two space-separated integers $$$l_i, r_i$$$ ($$$0 \le l_i \lt r_i \le 10^9$$$) — the start and end time in minutes of Johnny's $$$i$$$-th event on his calendar. It is guaranteed that no events have a nonzero time overlap, although events can share endpoints.

Output

Output a single integer — the maximum amount of time Johnny can run Claude Code for when he is away at events.

Examples
E. caffeinate
3 2 4
0 3
5 6
10 14
Output
7
Input
1 1 5
0 100
Output
5
Note

In the first sample test case, Johnny can run caffeinate at time $$$0$$$ and at time $$$10$$$. This ensures that his computer stays on for the entirety of events $$$1$$$ and $$$3$$$, which gives a total time of $$$7$$$ minutes.

In the second sample test case, Johnny can run caffeinate at time $$$50$$$ and keep his computer running for $$$5$$$ minutes.