IAEA a reglementat modul de construcție al noilor centrale nucleare. În jurul reactorului punctiform P se plasează K pereți din plumb în formă de cercuri concentrice, de raze naturale r1, r2, ..., rK-1, rK unități de măsură și cu grosimi neglijabile. Fiecare perete conține 109 piloni ușori din aluminiu egal depărtați. Pereții sunt plasați concentric și astfel încât pilonul cu indicele i de pe orice perete, pilonul cu indicele i de pe orice alt perete și reactorul P sunt coliniare.
Pentru a lăsa aerul să circule, se face un număr par de semne în dreptul pilonilor, iar pereții în formă de arce rezultați sunt mutați împreună cu stâlpii din interior la altă centrală. Rezultă N pereți sub formă de arce de cerc, cu piloni în capete.
Fiecare centrală nucleară construită după acest model are nevoie de reguli de evacuare de urgență comune. În caz de urgență, fizicienii se deplasează într-un grup compact cu viteză constantă, după cum urmează:
* sunt obligați să meargă de la reactor spre nord, spre primul perete (acesta există întotdeauna, dar se poate ajunge doar pe extremitatea lui, ceea ce se consideră ajungere pe respectivul perete),
* se pot deplasa doar pe partea interioară a unui perete, de-a lungul lui, parcurgând intervalul dintre doi piloni alăturați în r unități de timp, unde r este raza cercului suport al peretelui,
* se pot deplasa în linie dreaptă între un capăt de perete P1 și un punct P2 de pe un perete mai îndepărtat, astfel încât P, P1 și P2 sunt coliniare, câte o unitate la T secunde.
Figură: Exemplu de centrală văzută de sus: un drum corect parcurs pentru ieșirea din centrală este ilustrat cu roșu, iar pereții centralei sunt negri. Toți pilonii situați pe o rază au același indice și sunt folosiți pentru a marca începutul și sfârșitul unui perete. Sunt reprezentați câțiva piloni cu indici reprezentativi: 0 la nord, 25·107-1 la est, 50·107-1 la sud, 75·107-1 la vest.
Cerinţă
Scrieți un program care calculează timpul minim în secunde de evacuare a echipei de fizicieni, pornind de la reactor și oprindu-se la o extremitate (a unui perete de pe un cerc suport oarecare dintre cele K) de unde nu se mai poate urma procedura de evacuare în linie dreaptă.
Date de intrare
Fișierul de intrare centrala.in conține pe prima linie numerele naturale K și T. Pe următoarele K linii se găsesc informații despre cei N pereți sub formă de arce de cerc. Pe linia k+1 se găsesc: un număr natural rk ce reprezintă raza cercului al k-lea, un număr natural nenul nk care reprezintă numărul de arce de cerc rămase după tăierea celui de-al k-lea cerc și nk perechi de numere naturale. A j-a pereche reprezintă două valori uk.jvk.j. Valoarea uk.j este pilonul de la care s-a păstrat perete pentru al j-lea perete. Valoarea vk.j este pilonul până la care s-a păstrat perete. Dacă vk.j este peste 109-1, se consideră pilonul vk.j-109.
Date de ieşire
Fișierul de ieșire centrala.out va conține pe prima linie timpul minim de evacuare din centrală.
Restricţii
Pilonii de început (uk.j) și sfârșit (vk.j, respectiv vk.j-109) sunt distincți doi câte doi,
Între doi pereți de pe același cerc suport există măcar un interval de piloni liber,
Perechile de pe un cerc suport definesc pereții în sens orar, plecând de la pilonul cu indicele minim.
Rezultatul există întotdeauna și se încadrează într-un număr cu semn pe 64 biți. 1 ≤ K ≤ n1+n2+...+nK-1+nK = N ≤ 105 0 < T, r1, r2, ... rK-1, rK < 109 și ri < rj pentru i < j 0 ≤ uk.j < vk.j
Timpul parcurs de la reactor la peretele final este compus din timpul de mers în linie dreaptă și timpul de mers de-a lungul pereților. Timpul de mers în linie dreaptă este direct proporțional cu T și cu raza cercului suport al peretelui final. Mai exact, fizicienii pierd 100000000·(2+1+1) = 400000000 unități de timp. Pe primul nivel, ei parcurg 62500000 intervale de piloni spre est. Timpul necesar acestei deplasări depinde de raza cercului suport și este egal cu 62500000·2 = 125000000 unități. Fizicienii continuă drumul pe al doilea nivel spre extremitatea vestică, având nevoie de 187500000·3 = 562500000 unități de timp. Ei apoi parcurg nivelul al treilea (și ultimul), în 250000000·4 = 1000000000 unități de timp. Exemplul este ilustrat și în figură.
