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^\text{th}~ column $(1 \le i \le M)$ ~(1 \le i \le 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 \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$ ~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 \le N, M \le 100~

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

Subtask 2 [30%]

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

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

Subtask 3 [50%]

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

$0 \le K \le 4 \times 10^{10}$ ~0 \le K \le 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

Sample Output 1

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 $2$ ~2~, FatalEagle can harvest the last two rows for exactly $6$ ~6~ potatoes.

Sample Input 2

Sample Output 2

-1

Explanation for Sample Output 2

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

Comments

0

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

plot twist: FatalEagle is secretly selling the potato to techno

23

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?

-2

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

Lol

2

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

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

3

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

I think you use a tractor of zero width