potato field with exactly one potato on each unit square. Unfortunately, life isn't easy for : 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, 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.
so that he can harvest at least
potatoes.
Constraints
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
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 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 , 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
only has 4 potatoes left, and therefore cannot feed his family.
Comments
plot twist: FatalEagle is secretly selling the potato to techno
"family"
What kind of family consumes 4 * 10 ^ 10 potatoes in a season?
Lol
What do we do if
? Can we have a tractor with zero width?
I think you use a tractor of zero width