eolymp
bolt
Try our new interface for solving problems
Məsələlər

Avtobuslar

Avtobuslar

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Vasyuki rayonunun bəzi kəndləri arasında avtobus marşrutları fəaliyyət göstərir. Sərnişin axını çox böyük olmadığından avtobuslar gündə bir neçə dəfə işləyir.

Mariya İvanovna kənddən d kəndə v tez çatmaq istəyir (ehtimal olunur ki, 0 saatında o, d kənddədir).

Giriş verilənləri

Əvvəlcə kəndlərin ümumi sayı n(1 ≤ n ≤ 100), dv, sonra avtobus xətlərinin sayı verilmişdir. r(0 ≤ r ≤ 10000). Daha sonra avtobus səfərlərinin təsviri verildi. Hər bir marşrut başlanğıc kəndin nömrəsi, gediş vaxtı, təyinat kəndi və gəliş vaxtı ilə verilir (bütün vaxtlar 0-dan 10000-a qədər olan tam ədədlərdir). Sərnişin t vaxtında kəndə çatarsa, t-dan başlayaraq istənilən vaxt onu tərk edə bilər.

Çıxış verilənləri

Mariya İvanovnanın kəndə v çata biləcəyi minimum vaxtı çap edin. Əgər o, d-dan v-a getmək üçün bu avtobus səfərlərində uğursuz olarsa, -1 çıxın.

Nümunə

Giriş verilənləri #1
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
Çıxış verilənləri #1
5