Zadanie

Guľky

Počet bodov: 45, časový limit: 1000ms

Ako ste z názvu iste pochopili, táto úloha je o biliarde. Ste fascinovaný pohybom bilardových gulí a chceli by ste vedieť, kde sa konkrétna guľa nachádza v určitom čase.

V úlohe uvažujeme \(N\) guliek, očíslovaných od \(1\) po \(N\). Guľky stoja na stole s dĺžkou práve \(10^6\) metrov (jeho ľavý koniec má súradnicu \(0\) a pravý \(10^6\)). Na oboch koncoch stola sú bezodné dierky do ktorých guľky vedia spadnúť. Vašou úlohou je vypísať pozíciu jednej špecifikovanej guľky s číslom \(G\) po \(T\) sekundách.

Keďže toto je ešte jedna z tých ľahších úloh, všetky guľky budú mať rovnakú hmotnosť, všetky budú stáť na jednej priamke, každá guľka bude mať nulový polomer, nebudeme uvažovať rotáciu ani stratu energie a všetky zrážky budú dokonale pružné. Pre dokonale pružnú zrážku dvoch telies, platí nasledovný vzorec:

\[ v_{1}= \left({\frac {m_{1}-m_{2}}{m_{1}+m_{2}}}\right)u_{1}+ \left({\frac {2m_{2}}{m_{1}+m_{2}}}\right)u_{2} \]

\[ v_{2}= \left({\frac {m_{2}-m_{1}}{m_{1}+m_{2}}}\right)u_{2}+ \left({\frac {2m_{1}}{m_{1}+m_{2}}}\right)u_{1} \]

kde \(m_i\) je hmotnosť, \(u_i\) je rýchlosť pred zrážkou a \(v_i\) je rýchlosť guľe \(i\) po zrážke.

Vstup a výstup

Na vstupe máte na prvom riadku číslo \(N (1 \le N \le 10^5)\), počet guliek. Na druhom riadku je \(N\) celých čísel, počiatočné pozície guliek v metroch. Na treťom riadku je \(N\) celých čísel, počiatočné rýchlosti guliek v metroch za sekundu. (záporná rýchlosť reprezentuje pohyb doľava, kladná rýchlosť pohyb doprava). Štvrtý riadok bude obsahovať dve čísla - \(G\) a \(T\). Všetky čísla na vstupe budú v absolútnej hodnote najviac \(10^6\).

Na výstup vypíšte jedno číslo, pozíciu guličky s číslom \(G\) v čase \(T\). Výsledok zaokrúhlite na najbližšie celé číslo.

Príklad

Input:

1
6
-2
1 4

Output:

0

V čase 3 sa dokotúľa naša guľka na nultý meter, kde spadne do dierky a už tam ostane.

Input:

2
1 20
3 -3
2 2

Output:

14

Guľky sa za 2 sekundy nestihnú zraziť a guľka čislo 2 sa za daný čas pohne o 6 metrov doľava.