시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB111100.000%

문제

Velykų Zuikis turi M margučių, kuriuos jis nori įteikti N vaikų. Zuikio margučių visiems gali neužtekti, tačiau vaikai, gavę margutį, norės numarginti ir padovanoti po margutį kitiems vaikams – nesvarbu, ar margutį gavo nuo Zuikio, ar nuo kito vaiko. Dovanoti margutį vaikui galima tik jei jis dar neturi margučio. Zuikis žino, kam kiekvienas vaikas nori dovanoti margučius.

Panagrinėkime pavyzdį su penkiais vaikais. Paveikslėlyje rodyklės žymi, kam vaikai norėtų dovanoti margučius, patys gavę margutį:

Jeigu Zuikis padovanos margutį antrajam vaikui, šis vaikas numargins ir padovanos po margutį trečiajam ir pirmajam vaikui, o pirmasis – ketvirtajam vaikui. Ketvirtasis vaikas norėtų padovanoti margutį antrajam vaikui, bet nedovanos, kadangi šis margutį jau turi. Pastebėkime, kad nors Zuikis padovanojo tik vieną margutį, galiausiai margučius gavo net keturi vaikai.

Zuikis suprato, kad bendras margučius gausiančių vaikų skaičius priklauso nuo to, kuriems vaikams jis išdalins savo margučius. Raskite, kiek daugiausiai vaikų gali gauti dovanas, jeigu Velykų Zuikis protingai išdalins savo turimus margučius.

입력

Pirmojoje eilutėje bus pateiktas vaikų skaičius N ir Zuikio turimų margučių skaičius M.

Toliau bus pateikta N eilučių, aprašančių, kam kiekvienas vaikas norėtų dovanoti margučius, pats gavęs margutį. Vaikai numeruojami nuo 1 iki N.

Eilutėje, atitinkančioje i-tąjį vaiką, bus įrašytas sveikasis skaičius k, po kurio toje pačioje eilutėje bus įrašyta k sveikųjų skaičių – vaikų numerių, kuriems i-tasis vaikas, gavęs margutį, norės pats padovanoti po margutį.

Kiekvienam vaikui margutį dovanoti norės daugiausiai vienas vaikas. Taip pat, vaikas nenorės dovanoti margučio sau pačiam.

출력

Pirmojoje ir vienintelėje eilutėje išveskite vieną sveikąjį skaičių – didžiausią vaikų skaičių, kurie gaus margučius.

제한

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ N

서브태스크

번호배점제한
113

N ≤ 1 000, Kiekvienas vaikas dovanos margutį lygiai vienam vaikui

213

N ≤ 1 000, Duotame grafe nebus ciklų*

321

N ≤ 1 000, M = 1

421

N ≤ 1 000

532

N ≤ 100 000

*Ciklas susidaro tuomet, kai vaikas, padovanojęs margutį, dėl to pats iš kito vaiko gautų margutį. Pavyzdžiui, antrajame pavyzdyje tarp antrojo, pirmojo ir ketvirtojo vaiko susidarė ciklas.

예제 입력 1

3 2
2 2 3
0
0

예제 출력 1

3

Pirmą margutį Zuikis įteiks pirmajam vaikui, o pirmasis padovanos po margutį antrajam ir trečiajam. Antrą margutį Zuikis galės pasilikti sau, kadangi visi vaikai gavo margučius.

예제 입력 2

5 1
1 4
2 1 3
0
1 2
0

예제 출력 2

4

Testas sutampa su sąlygoje nagrinėtu pavyzdžiu.

채점 및 기타 정보

  • 예제는 채점하지 않는다.