AMPPZ-kilpailun tuomaristo koostuu viidestä henkilöstä, joiden tehtävänä on luoda mielenkiintoinen ja tasapainoinen kilpailu. Tänä vuonna lähetettiin $n$ tehtäväehdotusta, ja niistä on valittava $k$. Jokainen tuomari järjestää tehtävät toisistaan riippumatta subjektiivisen hienouden mukaan ja antaa niille pisteet, jotka muodostavat lukujen $1$:stä $n$:ään permutaation*. Tämän jälkeen kilpailuun valitaan automaattisesti $k$ tehtävää, joilla on korkein keskiarvo (aritmeettinen keskiarvo). Tasatilanteessa suositaan tehtäviä, joiden indeksi on pienempi.

Neljä tuomaria on jo arvostellut kaikki tehtävät. Viimeinen on tuomari Jerzy, joka pitää salaa laskennallisesta geometriasta ja haluaa AMPPZ-osallistujien kokevan sitä mahdollisimman paljon. Jokaisesta tehtävästä tiedetään, onko se geometriatehtävä ($x_i \in \{0, 1\}$), ja lisäksi tiedetään muiden tuomareiden antamat pisteet $a_i, b_i, c_i, d_i$. Jos Jerzy antaa pisteensä optimaalisesti (myös lukujen $1$:stä $n$:ään permutaationa), mikä on valittujen geometriatehtävien suurin mahdollinen lukumäärä?

*Lukujono missä tahansa järjestyksessä ilman toistoja — esimerkiksi $(5, 4, 3, 2, 1)$ tai $(2, 4, 1, 5, 3)$.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $k$ ($1 \le k \le n \le 200\,000$), jotka ilmaisevat lähetettyjen tehtävien lukumäärän ja kilpailuun valittavien tehtävien lukumäärän.

Seuraavat $n$ riviä kuvaavat lähetetyt tehtävät; $i$:nnellä rivillä on viisi kokonaislukua $x_i, a_i, b_i, c_i, d_i$ ($0 \le x_i \le 1$; $1 \le a_i, b_i, c_i, d_i \le n$), jotka kuvaavat $i$:ttä tehtävää. Arvo $x_i$ on $1$, jos tehtävä on geometria-aiheinen, ja muuten $0$. Seuraavat neljä lukua ovat muiden tuomareiden antamat pisteet. Jokainen tuomari antoi $n$ pareittain erisuurta pistemäärää, joten syötteessä jokainen sarake ensimmäistä lukuun ottamatta on lukujen $1$:stä $n$:ään permutaatio.

Tuloste

Tulosta yksi kokonaisluku – valittujen geometriatehtävien suurin mahdollinen lukumäärä.

Esimerkit

Syöte 1

5 3
1 3 5 5 2
0 5 2 4 5
1 2 3 3 4
1 1 1 1 1
0 4 4 2 3

Tuloste 1

2

Syöte 2

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

Tuloste 2

1

Huomautus

Ensimmäisessä esimerkissä tuomaristo valitsee kolme viidestä lähetetystä tehtävästä. Tehtävät $1$, $3$ ja $4$ käsittelevät geometriaa. Jerzy voi antaa viidelle tehtävälle pisteet $(4, 5, 3, 1, 2)$:

1. $x_1 = 1$; keskiarvo $\frac{3+5+5+2+4}{5} = 3.8$
2. $x_2 = 0$; keskiarvo $\frac{5+2+4+5+5}{5} = 4.2$
3. $x_3 = 1$; keskiarvo $\frac{2+3+3+4+3}{5} = 3$
4. $x_4 = 1$; keskiarvo $\frac{1+1+1+1+1}{5} = 1$
5. $x_5 = 0$; keskiarvo $\frac{4+4+2+3+2}{5} = 3$

Tehtävät $1$, $2$ ja $3$ valitaan kilpailuun (tehtävillä $3$ ja $5$ on sama keskiarvo, mutta tehtävällä $3$ on pienempi indeksi). Kolmesta valitusta tehtävästä kaksi on geometriatehtäviä. Jerzy ei voi saada valituksi enempää kuin kaksi geometriatehtävää, joten vastaus on $2$.

Toisessa esimerkissä Jerzy ei voi saada molempia geometriatehtäviä valituiksi. Molempien pitäisi saada korkein pistemäärä $4$, mikä on mahdotonta, koska Jerzyn pisteiden on oltava pareittain erisuuria.