Bessie מגישה שיעורי בית של $C$ קורסים ב־Moo U ($1 \le C \le 1{,}000$), כדי להעלות גירה עם חברים בזמן המתנה לאוטובוס הביתה.
מורים מקבלים רק אחרי שיעור, ניקוי לוח, סידור ציוד מעבדה וכו׳. הקלט נותן זמן מוקדם ביותר לקבלה.
מתחילה בקצה מסדרון $H$ מטר ($1 \le H \le 1{,}000$), מרחק $0$, הולכת מטר לשנייה לכיתות בסדר לבחירה. כיתות ודלת לאזור האוטובוסים במסדרון.
בהינתן מיקומי יציאה/כיתות ומועדים, מצאו יציאה מוקדמת ביותר להמתנה. כל המטלות לפני יציאה, הגשה בלי זמן.
קלט
- שורה 1: שלמים $C$, $H$, $B$. $B$ ($0 \le B \le H$), מרחק מהכניסה להמתנה.
- שורות $2..C+1$: שני שלמים לכיתת הגשה, ראשון ($0..H$), מטרים מהכניסה, שני ($0..10,000$), שנייה ראשונה לקבלת המורה.
פלט
- שורה 1: שלם, שנייה מוקדמת ביותר ליציאה להמתנת אוטובוסים.
דוגמאות
קלט 1
4 10 3
8 9
4 21
3 16
8 12פלט 1
22הערה
| זמן | פעולה |
|---|---|
| $0$ | Bessie הולכת לכיתות ב־$8$ מטר (ב־$8$מ׳) |
| $8$ | מחכה$1$ שנייה |
| $9$ | מגישה מטלה ראשונה |
| $9$ | מחכה$3$ שניות, חושבת על חציר קריר בקיץ |
| $12$ | מגישה מטלה אחרת כאן |
| $12$ | חוזרת לכיתה ב־$4$ מטר (ב־$4$מ׳) |
| $16$ | מחכה$5$ שניות, חושבת על שור נאה שפגשה |
| $21$ | מגישה מטלה |
| $21$ | חוזרת לכיתה ב־$1$ מטר (ב־$3$מ׳) |
| $22$ | מגישה מטלה |
| $22$ | יוצאת, כאן גם יציאת האוטובוס |
יוצאת ב־$22$, אין סידור טוב יותר.
תודות: Hal Burch, 2004