erinaceida

Erinaceidul Matei are o gradină împărțită în parcele sub forma unui tablou bidimensional, liniile și coloanele grădinii sunt numerotate începând cu 0.

În grădină se găsesc N fructe, fie mere, fie pere. Al i-lea fruct poate fi descris printr-un triplet $(x_i, y_i, z_i)$, reprezentând linia, coloana și tipul fructului (1 pentru mere și 2 pentru pere). Fiecare fruct se găsește în centrul unei parcele, iar în fiecare parcelă se poate afla maxim un fruct.

Inițial, Matei se află în parcela (0, 0) din grădină. El poate la orice moment de timp să se deplaseze fie pe linie, fie pe coloană cu o unitate (din parcela (x, y) el se poate deplasa fie în parcela (x + 1, y), fie în parcela (x, y + 1).

Cerință

Matei fiind un erinaceid hămesit, vrea să culeagă cât mai multe fructe. Totuși pentru a își menține o dietă balansată el vrea ca pentru o soluție cu număr maxim de fructe culese, diferență absolută dintre cantitatea de mere și pere culeasă să fie minimă.

Date de intrare

Pe prima linie se găsește numărul N ce reprezintă numărul de fructe din grădina lui Matei. Pe următoarele N linii se găsesc tripletele $(x_i, y_i, z_i)$.

Date de ieșire

Se vor afișa numărul maxim de fructe culese și diferență absolută minimă.

Restricţii

• 1 ≤ N ≤ 35 000
• $1 ≤ x_i, y_i ≤ N$ pentru orice 1 ≤ i ≤ N
• $z_i ∈ \{1, 2\}$ pentru orice 1 ≤ i ≤ N

Subtask 1 (5 puncte)

• 1 ≤ N ≤ 100

Subtask 2 (5 puncte)

• 1 ≤ N ≤ 400

Subtask 3 (10 puncte)

• 1 ≤ N ≤ 3 500

Subtask 4 (15 puncte)

• 1 ≤ N ≤ 5 000

Subtask 5 (25 puncte)

• 1 ≤ N ≤ 15 000

Subtask 6 (40 puncte)

• 1 ≤ N ≤ 35 000

Exemple

stdin

4
1 3 1
2 4 1
3 1 2
4 2 2

stdout

2 2

Explicații

O soluție posibilă este:
$\\ \text{X \ O \ O \ O \ O} \\ \text{X \ O \ O} \ \text{\color{red}{ O} } \ \text{O } \\ \text{X \ O \ O \ O } \ \text{\color{red}{O}} \\ \text{X } \ \text{\color{lime}{X }} \text {\ X \ O \ O} \\ \text{O \ O } \ \text{\color{lime}{X} } \ \text {O \ O \\}$

Cu X s-a notat drumul parcurs de Matei, cu $\color{red}{rosu}$ s-au marcat parcelele ce conțin mere și cu $\color{lime}{galben}$ s-au marcat parcelele ce conțin pere.