Dómnefnd AMPPZ samanstendur af fimm manns sem bera ábyrgð á því að búa til áhugaverða og jafnvæga keppni. Á þessu ári voru $n$ dæmatillögur sendar inn og velja þarf $k$ þeirra. Hver dómari raðar dæmunum sjálfstætt eftir huglægum töffaraskap og gefur þeim stig sem mynda umröðun* talnanna frá $1$ til $n$. Síðan velur keppnin sjálfkrafa þau $k$ dæmi sem hafa hæstu meðaleinkunn (reikningslegt meðaltal). Ef dæmi eru jöfn að stigum eru dæmi með lægri vísa tekin fram yfir.

Fjórir dómarar hafa þegar gefið öllum dæmunum einkunn. Sá síðasti er dómarinn Jerzy, sem heldur í laumi upp á reiknirúmfræði og vill að þátttakendur í AMPPZ fái að upplifa sem mest af henni. Fyrir hvert dæmi vitum við hvort það snýst um rúmfræði ($x_i \in \{0, 1\}$), og við vitum stigin frá hinum dómurunum $a_i, b_i, c_i, d_i$. Ef Jerzy úthlutar stigum sínum á besta mögulega hátt (einnig umröðun talnanna frá $1$ til $n$), hver er þá mesta mögulega fjöldi rúmfræðidæma sem valin verða?

*Runa í hvaða röð sem er, án endurtekninga — til dæmis $(5, 4, 3, 2, 1)$ eða $(2, 4, 1, 5, 3)$.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($1 \le k \le n \le 200\,000$), sem tákna annars vegar fjölda innsendra dæma og hins vegar fjölda dæma sem á að velja fyrir keppnina.

Næstu $n$ línur lýsa innsendu dæmunum; $i$-ta línan inniheldur fimm heiltölur $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$), sem lýsa $i$-ta dæminu. Gildið $x_i$ er jafnt $1$ ef dæmið er með rúmfræðiþema, en $0$ annars. Næstu fjórar tölurnar eru stigin sem hinir dómararnir gáfu. Hver dómari gaf $n$ innbyrðis ólík stig, þannig að í inntakinu er hver dálkur nema sá fyrsti umröðun talnanna frá $1$ til $n$.

Úttak

Prentaðu eina heiltölu – mesta mögulega fjölda valinna rúmfræðidæma.

Dæmi

Inntak 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

Úttak 1

2

Inntak 2

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

Úttak 2

1

Athugasemd

Í fyrra dæminu velur dómnefndin þrjú af fimm innsendum dæmum. Dæmi $1$, $3$ og $4$ fjalla um rúmfræði. Jerzy getur gefið dæmunum fimm stigin $(4, 5, 3, 1, 2)$:

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

Dæmi $1$, $2$ og $3$ verða valin í keppnina (dæmi $3$ og $5$ eru með sama meðaltal, en dæmi $3$ hefur lægri vísi). Tvö af þremur völdum dæmum eru rúmfræðidæmi. Jerzy getur ekki fengið fleiri en tvö rúmfræðidæmi valin, svo svarið er $2$.

Í seinna dæminu getur Jerzy ekki fengið bæði rúmfræðidæmin valin. Þau þyrftu bæði að fá hæstu einkunnina $4$, sem er ómögulegt vegna þess að stig Jerzys verða að vera innbyrðis ólík.