FatalEagle is a diligent farmer who owns a ~N \times M~ potato field with exactly one potato on each unit square. Unfortunately, life isn't easy for FatalEagle: while he was away trading on the market, some farmers who were jealous of his bountiful land came and destroyed some of his potatoes. These mysterious foes worked in a methodical manner, destroying some potatoes from every column of the farm. In the ~i^{th}~ column ~(1 \le i \le M)~, the jealous farmers destroyed all the potatoes from row ~a_i~ to row ~b_i~ ~(1 \le a_i \le b_i \le N)~, inclusive.

When the time came for the annual harvest, FatalEagle found that he was too busy plotting his revenge. However, he still needs to harvest at least ~K~ potatoes to feed his family. So he decided that he would buy a tractor of width ~W~, drive it through his field horizontally exactly once, and collect any of the remaining potatoes from ~W~ consecutive rows.

FatalEagle doesn't have a lot of money to spend on a tractor, so he would like to know the minimal ~W~ so that he can harvest at least ~K~ potatoes.

Constraints

Subtask 1 [20%]

~1 \le N, M \le 100~

~0 \le K \le 10\,000~

Subtask 2 [30%]

~1 \le N, M \le 3\,000~

~0 \le K \le 9\,000\,000~

Subtask 3 [50%]

~1 \le N, M \le 200\,000~

~0 \le K \le 4 \times 10^{10}~

Input Specification

The first line of input will contain three space-separated integers, ~N~, ~M~, and ~K~.

The next ~M~ lines will each contain two space-separated integers, ~a_i~ and ~b_i~.

Output Specification

Output one integer, the minimal ~W~ such that FatalEagle can still harvest at least ~K~ potatoes. If it is impossible, output -1.

Sample Input 1

5 5 6
2 5
1 3
4 5
3 3
1 2

Sample Output 1

2

Explanation for Sample Output 1

The field looks like this, where P represents a potato:

P.PP.
..PP.
..P.P
.P.PP
.P.PP

With a tractor of width ~2~, FatalEagle can harvest the last two rows for exactly ~6~ potatoes.

Sample Input 2

3 4 7
2 3
1 2
1 3
2 2

Sample Output 2

-1

Explanation for Sample Output 2

Poor FatalEagle only has 4 potatoes left, and therefore cannot feed his family.