DMOPC '15 Contest 6 P3 - Harvest

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

FatalEagle is a diligent farmer who owns an 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^\text{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.


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


Explanation for Sample Output 1

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


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


Explanation for Sample Output 2

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


  • -1
    Evanhyd  commented on Jan. 3, 2021, 5:57 a.m. edit 3

    plot twist: FatalEagle is secretly selling the potato to techno

  • 22
    NT_AUTHORITY_SYSTEM  commented on June 21, 2017, 4:02 p.m. edited


    What kind of family consumes 4 \times 10^{10} potatoes in a season?

    • -1
      nikos  commented on Sept. 25, 2017, 7:15 p.m.


  • 2
    nullptr  commented on March 2, 2016, 12:58 a.m.

    What do we do if K=0? Can we have a tractor with zero width?

    • 4
      Zander  commented on March 2, 2016, 1:11 a.m.

      I think you use a tractor of zero width