Circles

Pe un teren agricol de lângă orașul Austin, din statul Texas, există $N$ traiectorii, numerotate: $1, 2, \ldots, N$, pe care se pot utiliza tractoare. Traiectoriile sunt disjuncte între ele oricare două și au forma unor cercuri de raze ce au lungimile valori numere naturale nenule. Sensul deplasării pe fiecare traiectorie este descris prin trei puncte distincte (din sistemul de coordonate carteziene) de pe traiectorie, în ordinea în care acestea sunt vizitate de către tractor. Astfel, dacă un tractor urmează traiectoria $i$, atunci tractorul este pornit din punctul $(x_{i, 1}, y_{i, 1})$, ajunge în $(x_{i, 2}, y_{i, 2})$, apoi în $(x_{i, 3}, y_{i, 3})$ și, în final, se întoarce în $(x_{i, 1}, y_{i, 1})$, unde tractorul este oprit, efectuându-se exact o rotație completă pe cerc.

Fiecare traiectorie $i$ dintre cele $N$ are asociată o valoare $V(i)$ egală cu: $V(i) = r(i) \cdot r(i) \cdot w(i)$, unde $r(i)$ reprezintă lungimea razei cercului ce descrie traiectoria $i$, iar $w(i) = 1$, dacă deplasarea pe traiectoria $i$ se face în sens antiorar (adică invers acelor de ceas) sau $w(i) = -1$, dacă deplasarea se face în sens orar.

Aflați în vacanță la casele din Austin ale bunicilor, Sam și John vor să ajute la îngrijirea terenului agricol. Astfel, Sam își alege o mulțime nevidă $A = \{a_1, a_2, \ldots, a_k\}$ alcătuită din $k$ traiectorii distincte dintre cele $N$ ($1 \leq k < N$), iar lui John îi rămâne mulțimea nevidă $B = \{b_1, b_2, \ldots, b_{N-k}\}$ alcătuită din restul de $(N-k)$ traiectorii nealese de Sam.

Bineînțeles, munca lor este răsplătită în funcție de performanță, astfel că după ce fiecare termină de utilizat tractoarele pe traiectoriile alese, Sam primește: $k \cdot (V(a_1) + V(a_2) + \ldots + V(a_k))$ puncte la sala de bowling, iar John primește: $(N-k) \cdot (V(b_1) + V(b_2) + \ldots + V(b_{N-k}))$ puncte. Este posibil ca punctajul obținut să fie mai mic sau egal decât $0$.

Cerință

Pentru a asigura echilibrul între cele două punctaje obținute, bunicii aleg un număr natural $L$. Determinați în câte moduri distincte își pot împărți cei doi tineri cele două mulțimi de traiectorii $A$ și $B$, astfel încât valoarea absolută a diferenței dintre punctajul obținut de Sam și respectiv punctajul obținut de John să fie mai mică sau egală decât numărul $L$.

Date de intrare

Pe prima linie se află numărul natural $N$, cu semnificația de mai sus.
Pe fiecare dintre următoarele $N$ linii se află, separate între ele prin câte un spațiu, câte șase numere naturale; astfel, pe a $(i+1)$-a linie se află, în ordine, valorile $x_{i, 1}$, $y_{i, 1}$, $x_{i, 2}$, $y_{i, 2}$, respectiv $x_{i, 3}$, $y_{i, 3}$, pentru fiecare $i$: $1 \leq i \leq N$. Pe următoarea linie se află numărul natural $L$.

Date de ieșire

Pe prima linie se află un singur număr întreg, reprezentând numărul de moduri distincte determinat. În cazul în care nu există niciun astfel de mod, atunci valoarea acestui număr va fi egală cu $-1$.

Restricții și precizări

• $2 \leq N \leq 34$ și $0 \leq L \leq 10^{17}$.
• $0 \leq x_{i, j}, y_{i, j} \leq 1 \ 000 \ 000$ și $x_{i, j}, y_{i, j}$ sunt numere naturale, pentru fiecare $(i, j)$: $1 \leq i \leq N$ și $1 \leq j \leq 3$.
• $r(i) > 0$ și $|V(i)| \leq 10^{12}$, pentru fiecare $i$: $1 \leq i \leq N$.
• Cercurile ce descriu fiecare dintre cele $N$ traiectorii au coordonatele (abscisa și ordonata) centrului valori numere naturale mai mici sau egale decât $1 \ 000 \ 000$.
• O traiectorie circulară este alcătuită doar din punctele de pe conturul cercului ce descrie traiectoria, iar două traiectorii sunt disjuncte dacă cercurile ce le descriu nu au niciun punct în comun.
• Pentru un cerc $C$ de rază $r$ ($r > 0$), ce are centrul în punctul de coordonate $(x_C, y_C)$, toate punctele de pe cerc se află la aceeași distanță față de centru, egală cu lungimea razei. Astfel, $(x - x_C)^2 + (y - y_C)^2 = r^2$, pentru fiecare $(x, y) \in C$ (unde $x$ și $y$ sunt numere reale).
• În cadrul deplasării unui tractor pe traiectoria $i$, fiecare punct de coordonate reale de pe cercul ce descrie traiectoria este vizitat exact o singură dată, cu excepția punctului $(x_{i, 1}, y_{i, 1})$, care este vizitat de două ori: o dată la începutul deplasării și o dată la finalul deplasării.
• Intrarea la sala de bowling se plătește în puncte, nu în dolari.

Exemplul 1

stdin

3
0 1 1 0 2 1
7 14 13 6 10 5
14 10 12 12 12 8
30

stdout

-1

Explicație

Centrele cercurilor ce descriu cele $N = 3$ traiectorii se află în punctele $(1, 1)$, $(10, 10)$, respectiv $(12, 10)$. Cercurile au lungimile razelor egale cu $1$, $5$, respectiv $2$.

Prima traiectorie este descrisă de un cerc cu raza $r(1) = 1$ și este este în sens antiorar, astfel că $w(1) = 1$. Prin urmare, $V(1) = 1$. În mod similar, $V(2) = -25$ și $V(3) = 4$.

Există, în total, șase moduri distincte în care Sam și John își pot împărți cele două mulțimi nevide $A$ și $B$:

• Dacă $A = \{1\}$, iar $B = \{2, 3\}$, Sam primește un punct și John $(-42)$ de puncte. Valoarea absolută a diferenței $1 - (-42)$ este egală cu $43$.
• Dacă $A = \{1, 2\}$, iar $B = \{3\}$, Sam primește $(-48)$ de puncte și John $4$ puncte. Valoarea absolută a diferenței $(-48) - 4$ este egală cu $52$.
• Dacă $A = \{1, 3\}$, iar $B = \{2\}$, Sam primește $10$ puncte și John $(-25)$ de puncte. Valoarea absolută a diferenței $10 - (-25)$ este egală cu $35$.
• Dacă $A = \{2\}$, iar $B = \{1, 3\}$, Sam primește $(-25)$ de puncte și John $10$ puncte. Valoarea absolută a diferenței $(-25) - 10$ este egală cu $35$.
• Dacă $A = \{2, 3\}$, iar $B = \{1\}$, Sam primește $(-42)$ de puncte și John un punct. Valoarea absolută a diferenței $(-42) - 1$ este egală cu $43$.
• Dacă $A = \{3\}$, iar $B = \{1, 2\}$, Sam primește $4$ puncte și John $(-48)$ de puncte. Valoarea absolută a diferenței $4 - (-48)$ este egală cu $52$.

În acest exemplu, nu există niciun mod de a alege mulțimile $A$ și $B$, astfel încât valoarea absolută a diferenței dintre cele două punctaje să fie mai mică sau egală decât $L = 30$.

Exemplul 2

stdin

3
0 1 1 0 2 1
7 14 13 6 10 5
14 10 12 12 12 8
43

stdout

4

Explicație

Există patru moduri distincte de a alege mulțimile $A$ și $B$, astfel încât valoarea absolută a diferenței dintre cele două punctaje să fie mai mică sau egală decât $L = 43$, după cum urmează:

• $A = \{1\}$ și $B = \{2, 3\}$;
• $A = \{1, 3\}$ și $B = \{2\}$;
• $A = \{2\}$ și $B = \{1, 3\}$;
• $A = \{2, 3\}$ și $B = \{1\}$.