AMPPZ қазылар алқасы қызықты әрі теңгерімді жарыс құрастыруға жауапты бес адамнан тұрады. Биыл $n$ есеп ұсынысы түсті, солардың ішінен $k$ есепті таңдап алу керек. Әрбір қазы өз бетінше есептерді субъективті қызықтылығы бойынша реттеп, оларға $1$-ден $n$-ге дейінгі сандардың алмастыруын* құрайтын ұпайлар береді. Содан кейін жарыс жүйесі орташа ұпайы (арифметикалық ортасы) ең жоғары $k$ есепті автоматты түрде таңдайды. Ұпайлар тең болған жағдайда индексі кішірек есептерге басымдық беріледі.

Төрт қазы барлық есептерді бағалап қойды. Соңғысы — қазы Ежи; ол есептеу геометриясын жасырын ұнатады және AMPPZ қатысушыларының оны мүмкіндігінше көбірек кездестіргенін қалайды. Әр есеп үшін оның геометрия есебі екені не емес екені ($x_i \in \{0, 1\}$) және қалған қазылардың берген $a_i, b_i, c_i, d_i$ ұпайлары белгілі. Егер Ежи өз ұпайларын (ол да $1$-ден $n$-ге дейінгі сандардың алмастыруы) тиімді түрде үлестірсе, таңдап алынған геометрия есептерінің ең көп дегендегі мүмкін саны қанша болады?

*Қайталанбайтын, кез келген ретпен берілген тізбек — мысалы, $(5, 4, 3, 2, 1)$ немесе $(2, 4, 1, 5, 3)$.

Кіріс деректер

Бірінші жолда ұсынылған есептер санын және жарысқа таңдап алынатын есептер санын тиісінше білдіретін екі бүтін сан $n$ және $k$ ($1 \le k \le n \le 200\,000$) берілген.

Келесі $n$ жол ұсынылған есептерді сипаттайды; олардың $i$-шісінде $i$-ші есепті сипаттайтын бес бүтін сан $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$) берілген. Егер есеп геометрия тақырыбында болса, $x_i$ мәні $1$-ге, ал басқа жағдайда $0$-ге тең. Келесі төрт сан — қалған қазылар берген ұпайлар. Әрбір қазы өзара әртүрлі $n$ ұпай берген, сондықтан кіріс деректерде бірінші бағаннан басқа әрбір баған $1$-ден $n$-ге дейінгі сандардың алмастыруы болып табылады.

Шығыс деректер

Бір бүтін санды — таңдалған геометрия есептерінің ең көп дегендегі мүмкін санын шығарыңыз.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

2

Кіріс деректер 2

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

Шығыс деректер 2

1

Ескерту

Бірінші мысалда қазылар алқасы ұсынылған бес есептің үшеуін таңдайды. $1$, $3$ және $4$-ші есептер геометрияға қатысты. Ежи бес есепке $(4, 5, 3, 1, 2)$ ұпайларын бере алады:

1. $x_1 = 1$; орташа мәні $\frac{3+5+5+2+4}{5} = 3.8$
2. $x_2 = 0$; орташа мәні $\frac{5+2+4+5+5}{5} = 4.2$
3. $x_3 = 1$; орташа мәні $\frac{2+3+3+4+3}{5} = 3$
4. $x_4 = 1$; орташа мәні $\frac{1+1+1+1+1}{5} = 1$
5. $x_5 = 0$; орташа мәні $\frac{4+4+2+3+2}{5} = 3$

Жарысқа $1$, $2$ және $3$-ші есептер таңдалады ($3$ және $5$-ші есептердің орташа мәні бірдей, бірақ $3$-ші есептің индексі кіші). Таңдалған үш есептің екеуі — геометрия есептері. Ежи екі геометрия есебінен артық есептің таңдалуына қол жеткізе алмайды, сондықтан жауабы — $2$.

Екінші мысалда Ежи екі геометрия есебінің де таңдалуына қол жеткізе алмайды. Ол үшін екеуі де ең жоғары $4$ ұпайын алуы керек еді, бірақ Ежидің ұпайлары өзара әртүрлі болуы тиіс болғандықтан, бұл мүмкін емес.