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
dangerous button do not press
It's funny that with the current data, if
is not treated appropriately, you could pass the last 2 subtasks but not the first.
plot twist: FatalEagle is secretly selling the potato to techno
"family"
What kind of family consumes
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