Bessie oddaje zadania $C$ zajęć Moo U ($1 \le C \le 1{,}000$), by przeżuwać z kolegami czekając na autobus do domu.
Nauczyciele przyjmują po zajęciach, czyszczeniu tablicy, odłożeniu przyborów laboratoryjnych itd. Wejście daje najwcześniejszy odbiór.
Start z końca korytarza $H$ metrów ($1 \le H \le 1{,}000$), odległość $0$, metr/sekundę do sal w dowolnej kolejności. Sale i drzwi do oczekiwania na autobus są przy korytarzu.
Położenia wyjścia/sal i rozkłady dają najwcześniejsze wyjście do oczekiwania. Wszystko oddać przed, samo oddanie bez czasu.
Wejście
- Wiersz 1: całkowite $C$, $H$, $B$. $B$ ($0 \le B \le H$), odległość wejście-oczekiwanie.
- Wiersze $2..C+1$: dwie całkowite dla sali, pierwsza ($0..H$), metry od wejścia, druga ($0..10,000$), pierwsza sekunda przyjmowania przez nauczyciela.
Wyjście
- Wiersz 1: całkowite, najwcześniejsza sekunda wyjścia do oczekiwania.
Przykład
Wejście 1
4 10 3
8 9
4 21
3 16
8 12Wyjście 1
22Uwagi
| Czas | Czynność |
|---|---|
| $0$ | Bessie idzie do sal na$8$ metrze (na$8$m) |
| $8$ | Czeka$1$ sekundę |
| $9$ | Oddaje pierwsze zadania |
| $9$ | Czeka$3$ sekundy, myśli o chłodnym letnim sianie |
| $12$ | Oddaje pozostałe zadania tutaj |
| $12$ | Wraca do sali na$4$ metrze (na$4$m) |
| $16$ | Czeka$5$ sekund, myśli o poznanym przystojnym byku |
| $21$ | Oddaje zadania |
| $21$ | Wraca do sali na$1$ metrze (na$3$m) |
| $22$ | Oddaje zadania |
| $22$ | Wychodzi, tu też wyjście do autobusu |
Wychodzi w $22$, lepszego planu nie ma.
Podziękowania: Hal Burch, 2004