DMOPC '15 Contest 6 P3 - Harvest - DMOJ: Modern Online Judge

DMOPC '15 Contest 6 P3 - Harvest

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 128M

Author:

Problem type

FatalEagle is a diligent farmer who owns an $N \times M$ $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}$ $i^{th}$ column $(1 \le i \le M)$ $(1 \leq i \leq M)$ , the jealous farmers destroyed all the potatoes from row $a_i$ $a_{i}$ to row $b_i$ $b_{i}$ $(1 \le a_i \le b_i \le N)$ $(1 \leq a_{i} \leq b_{i} \leq 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$ $K$ potatoes to feed his family. So he decided that he would buy a tractor of width $W$ $W$ , drive it through his field horizontally exactly once, and collect any of the remaining potatoes from $W$ $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$ $W$ so that he can harvest at least $K$ $K$ potatoes.

Constraints

Subtask 1 [20%]

$1 \le N, M \le 100$ $1 \leq N, M \leq 100$

$0 \le K \le 10\,000$ $0 \leq K \leq 10 000$

Subtask 2 [30%]

$1 \le N, M \le 3\,000$ $1 \leq N, M \leq 3 000$

$0 \le K \le 9\,000\,000$ $0 \leq K \leq 9 000 000$

Subtask 3 [50%]

$1 \le N, M \le 200\,000$ $1 \leq N, M \leq 200 000$

$0 \le K \le 4 \times 10^{10}$ $0 \leq K \leq 4 \times 10^{10}$

Input Specification

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

The next $M$ $M$ lines will each contain two space-separated integers, $a_i$ $a_{i}$ and $b_i$ $b_{i}$ .

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

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

Copy

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

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

Sample Input 2

Copy

Sample Output 2

Copy

-1

Explanation for Sample Output 2

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

Comments

0

WinDogeNT commented on Dec. 9, 2024, 2:03 p.m.

dangerous button do not press

0

Humanthe2nd commented on Dec. 9, 2024, 12:46 a.m.

It's funny that with the current data, if $K = 0$ $K = 0$ is not treated appropriately, you could pass the last 2 subtasks but not the first.

0

Evanhyd commented on Jan. 3, 2021, 5:57 a.m. ← edit 3 →

plot twist: FatalEagle is secretly selling the potato to techno

24

NT_AUTHORITY_SYSTEM commented on June 21, 2017, 4:02 p.m. ← edited →

"family"

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