Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_1et_internetas_vyr.in

Rezultatų failas: lmio_2018_1et_internetas_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Internetas

Tomo internetas veikia prastai – kartais ryšys ima ir pradingsta. Tomas nori sužinoti, kiek jam gali tekti laukti, kol pradingęs interneto ryšys vėl atsiras, todėl laikas nuo laiko jis patikrina ir pasižymi ar turi interneto ryšį tuo momentu.

Tomas prisimena, kad pirmo ir paskutinio matavimo metu jis interneto ryšį turėjo.

Užduotis

Padėkite Tomui sužinoti, kiek ilgiausiai laiko jis galėjo neturėti interneto.

Pradiniai duomenys

Pirmoje eilutėje yra pateiktas vienas sveikasis skaičius N – matavimų, kuriuos atliko Tomas, kiekis.

Kiekvienoje iš N tolimesnių eilučių yra pateikti 2 sveikieji skaičiai: T_i – laikas, kuriuo Tomas įvykdė i-tąjį matavimą, ir M_i – atlikto matavimo rezultatas. M_i yra 1, jei matavimo metu interneto ryšys buvo, arba 0, jei tuo metu interneto ryšio Tomas neturėjo.

Matavimai yra pateikti T_i didėjimo tvarka.

Rezultatai

Išveskite vieną sveikąjį skaičių – ilgiausią laiko tarpą, kurio metu Tomas galėjo neturėti interneto.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
6
1 1
3 0
4 1
5 0
6 0
8 1
 
4
 
Ilgiausias galimas laiko tarpas be interneto yra tarp 4 ir 8 - interneto ryšys pradingo vos tik po matavimo atlikto 4 laiko metu, o atsirado prieš pat matavimą, atliktą 8 laiko metu
 
4
1 1
2 1
4 1
7 1
 
3
 
Nors ir visų matavimų metu Tomas turėjo interneto ryšį, jis nežino, ar jį turėjo tarp matavimų. Ilgiausias galimas laiko tarpas be interneto yra tarp 3 ir 4 matavimų

Ribojimai

2\\leqN\\leq1000,1\\leqT_i\\leq1000000,T_i<T_{i+1}