TLE '15 P2 - Microwaves - Olympiads Online Judge

TLE '15 P2 - Microwaves

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 128M

Authors:

Problem type

Today is a special day since TT1103 isn't going to buy lunch at a nearby restaurant! His parents ran out of money, so he had to bring a microwavable lunch today.

Pierre Elliott Trudeau High School is also famous for its faulty microwaves. There are many microwaves available, but only a few of them actually heat up food. Today, $N$ $N$ $(1 \le N \le 100)$ $(1 \leq N \leq 100)$ microwaves are functional, and TT1103 needs to microwave his food for $T$ $T$ $(1 \le T \le 1\,000\,000)$ $(1 \leq T \leq 1 000 000)$ minutes.

There are also $M$ $M$ $(1 \le M \le 100\,000)$ $(1 \leq M \leq 100 000)$ people in the cafetorium today who need to microwave their food, named $1$ $1$ to $M$ $M$ . People must wait in a line in order to use the microwaves, and people are not allowed to cut in front of others. The $i^\text{th}$ $i^{th}$ person will go to the back of the line $t_i$ $t_{i}$ $(0 \le t_i \le 1\,000\,000)$ $(0 \leq t_{i} \leq 1 000 000)$ minutes after lunch starts, and needs to microwave food for $f_i$ $f_{i}$ $(1 \le f_i \le 1\,000\,000)$ $(1 \leq f_{i} \leq 1 000 000)$ minutes.

Immediately after a person is done using a microwave, somebody else can use it. If there are microwaves available, the person at the front of the line can either wait, or leave the line and choose a microwave. Only the person at the front of the line can exit the line and choose a microwave. If no microwaves are available, then the person at the front of the line must wait. Each microwave can only serve 1 person, nobody can interrupt their turn at a microwave, and it is guaranteed that no two people will arrive at the exact same time.

TT1103 is a nice person, so he doesn't want to inconvenience people. As such, TT1103 will only microwave his food if at all times during $T$ $T$ continuous minutes:

The person at the front of the line waits $0$ $0$ minutes after reaching the front before going to an available microwave.
or
There is nobody in the line.

You are tasked with guiding people to an available microwave or telling them to wait. If you guide people in an optimal way, what is the minimal number of minutes after the start of lunch until TT1103 can microwave his lunch?

Input Specification

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

$M$ $M$ lines of input follow. The $i^\text{th}$ $i^{th}$ line will contain two space-separated integers, $t_i$ $t_{i}$ and $f_i$ $f_{i}$ .

Output Specification

A single integer specifying the minimal number of minutes after the start of lunch, showing when TT1103 can microwave his food.

Sample Input 1

Copy

2 2 5
0 5
3 1

Sample Output 1

Copy

Explanation for Sample Output 1

TT1103 can microwave his lunch 4 minutes after lunch starts by taking his turn after the second person is done.

Sample Input 2

Copy

Sample Output 2

Copy

Explanation for Sample Output 2

TT1103 cannot microwave his lunch before person 1 or person 2, since others will need to wait for him to finish, but if TT1103 microwaves his food immediately after person 2 is done, TT1103 will be done just as person 3 enters the line.

Sample Input 3

Copy

1 2 3
0 5
1 3

Sample Output 3

Copy

Explanation for Sample Output 3

Person 2 cannot microwave his food before person 1 is done, so he will not start until 5 minutes after lunch starts. Thus, TT1103 cannot start microwaving his food until 8 minutes after lunch starts.

Comments

8

4fecta commented on Aug. 13, 2019, 9:53 p.m.

Don't you just hate it when your school only has 100 operational microwaves?

-16

Kirito commented on April 6, 2016, 4:30 a.m. ← edited →

If his parents are out of money, where did he get the lunch from? o_O

This comment is hidden due to too much negative feedback. Show it anyway.

28

TT1103 commented on April 7, 2016, 1:41 a.m. ← edited →

ZQFMGB12 gave me some of his cold leftovers.