## DMOPC '15 Contest 6 P3 - Harvest

View as PDF

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

Author:
Problem type

FatalEagle is a diligent farmer who owns a 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 column , the jealous farmers destroyed all the potatoes from row to row , 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 potatoes to feed his family. So he decided that he would buy a tractor of width , drive it through his field horizontally exactly once, and collect any of the remaining potatoes from consecutive rows.

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

#### Input Specification

The first line of input will contain three space-separated integers, , , and .

The next lines will each contain two space-separated integers, and .

#### Output Specification

Output one integer, the minimal such that FatalEagle can still harvest at least 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 , FatalEagle can harvest the last two rows for exactly 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.

• NT_AUTHORITY_SYSTEM  commented on June 21, 2017, 12:02 p.m.

"family"

What kind of family consumes 4 * 10 ^ 10 potatoes in a season?

• nikos  commented on Sept. 25, 2017, 3:15 p.m.

Lol

• cheesecake  commented on March 1, 2016, 9:53 p.m.

Sorry about the confusion with Sample Input 2, the explanation has been corrected.

• nullptr  commented on March 1, 2016, 8:24 p.m.

I don't understand sample input 2. Aren't there only 4 potatoes left?

• minecraftyugi  commented on March 1, 2016, 8:24 p.m.

In sample input 2, how are there 6 potatoes left? If 2 are removed in the first column, 2 in the second, 3 in the third and 1 in the fourth, doesnt that leave 4 potatoes?

• nullptr  commented on March 1, 2016, 7:58 p.m.

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

• Zander  commented on March 1, 2016, 8:11 p.m.

I think you use a tractor of zero width