Bob Ross este foarte faimos pentru picturile sale în ulei cu peisaje muntoase. Astăzi s-a hotărât să picteze o nouă operă, dar va aborda procesul său de creație într-un mod inedit.

Bob dispune de N puncte pe o pânză infinită, al i-lea punct având coordonatele (x[i], y[i]). Punctele au proprietatea că x[i] < x[i+1]. El își va alege un număr de puncte și pentru fiecare punct ales i, va colora segmentele dintre perechile de puncte (i - 1, i) și (i, i+1).

Alegând o submulțime a celor N puncte, el va colora segmentele incidente acestor puncte în următorul mod: de fiecare dată când își alege un punct, va colora segmentele incidente cu acel punct (orice punct are doi vecini, cu excepția primului și ultimului punct, care au doar un vecin). Dacă un segment este deja colorat, atunci nu va fi colorat a doua oară, și nici cantitatea de vopsea de pe pensulă nu va scădea.

Inițial, Bob are o pensulă cu o cantitate V de vopsea. Cantitatea de vopsea necesară pentru a colora un segment este egală cu pătratul lungimii acelui segment, iar după colorare cantitatea de vopsea de pe pensulă scade cu această valoare.

Cerința

Bob s-a gândit la următoarele K scenarii. Dacă la scenariul i ar avea o pensulă cu o cantitate V[i] de vopsea, care este numărul maxim P[i], astfel încât oricum am alege P[i] puncte, să poată colora toate segmentele adiacente acelor puncte?

Date de intrare

Prima linie din fișierul de intrare ross.in va conține un singur număr N reprezentând numărul de puncte de pe pânza lui Bob. Pe următoarele N linii se vor afla câte 2 numere x[i], y[i] separate printr-un spațiu, reprezentând coordonatele punctului i. Pe următoarea linie se află numărul K de scenarii ale lui Bob. Pe următoarele K linii se va afla câte un număr V[i] reprezentând cantitatea de vopsea de pe pensulă pentru scenariul i.

Date de ieșire

Fișierul de ieșire ross.out va conține K linii, linia i având un singur număr P[i] reprezentând răspunsul pentru scenariul i.

Restricții și precizări

• 1 ≤ N ≤ 2.000
• 1 ≤ K ≤ 100.000
• 1 ≤ x[i], y[i] ≤ 1.000.000
• 0 ≤ V[i] ≤ 1015
• x[i] < x[i+1], pentru orice i ∊ {1, 2, ..., N-1}.

Exemplu:

ross.in

6
2 2
4 4
5 1
7 6
8 5
10 2
2
44
55

ross.out

1
2

Explicație

Pentru V = 44 răspunsul este 1. Oricum am alege un punct, putem colora segmentele adiacente acestuia. Există totuși perechi de 2 puncte, care pentru colorare, necesită o cantitate de vopsea mai mare decât 44 (spre exemplu, alegând punctele (5, 1) și (10, 2), avem nevoie de o pensulă cu o cantitate de vopsea mai mare sau egală ca 52).

Pentru V = 55 răpsunsul este 2. Pentru oricare 2 perechi de puncte alese, cantitatea de de vopsea necesară este mai mică sau egală cu 55. Alegând punctele (4, 4), (7, 6) și (10, 2), costul colorării depașește 55, deci răspunsul este 2.