시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB198847.059%

문제

그렘린은 작고, 재미있고, 털이 보송보송한 상상 속의 요정이다. 그렘린의 종류는 N가지이며, 편의상 종류별로 1번 부터 N번까지 차례대로 번호가 매겨져있다.

T년 전 한 연구소에서 폭발이 일어나 N 종류의 그렘린이 한 마리씩 생겨났다. 그렘린은 두 단계의 성장 과정(알 → 성장기)을 지나 완전히 자란다.

종류가 i인 그렘린은 알에서 부화하고 Yi년 동안 성장기를 지난다. 성장을 완전히 마친 그렘린은 완전한 성장 직후 Ki개의 알을 낳는다. 각 알 별로 태어나는 그렘린 종류가 다를 수 있고, 알이 부화하는데 걸리는 시간도 다를 수 있다. 안타깝게도 그렘린은 알을 다 낳고 죽는다.

폭발이 일어나고 T년이 지난 현재, 과학자들은 여태까지 존재했던 그렘린 중에 조상이 가장 많은 그렘린이 궁금해졌다. 다만 과학자들은 아직 부화하지 않은 그렘린은 고려하지 않는다. 여기서 조상이란, 부모, 부모의 부모, 부모의 부모의 부모, ... 만 고려한다. 올해 부화 예정인 알들은 모두 부화되었다고 봐도 무방하다.

과학자들을 도와 가장 조상이 많은 그렘린의 조상수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 그렘린 종류의 수 N과 폭발이 일어난 뒤 지난 년 수 T가 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 1015)

다음 3N개의 줄에 그렘린 종류에 대한 입력이 주어진다.

  • 첫 줄에는 자연수 Ki와 Yi가 주어진다. (1 ≤ Ki ≤ 1000, 1 ≤ Yi ≤ 1000) Ki는 부화하는 알의 개수이고, Yi는 i번 종류의 그렘린이 부화한 뒤 성장기를 거치는 기간을 의미한다.
  • 둘째 줄에는 각 알이 부화되고 나오는 그렘린의 종류를 나타내는 Ki개의 자연수가 주어진다.
  • 셋째 줄에는 각 알이 부화하는데 걸리는 년 수가 주어진다. 이는 1이상 1000 이하의 값이다.

출력

첫 줄에 가장 조상이 많은 그렘린의 조상의 수를 출력한다.

예제 입력 1

1 42
1 10
1
5

예제 출력 1

2

예제 입력 2

2 42
1 10
1
5
1 5
1
5

예제 출력 2

3

2번 종류 그렘린이 폭발이 일어난 뒤 5년째에 알을 낳고 죽는다.

그 알은 10년째에 부화되어 1번 종류 그렘린이 나온다. 이 그렘린은 20년째에 알을 낳고 죽는다.

그 알은 25년째에 부화되어 1번 종류 그렘린이 나온다. 이 그렘린은 35년째에 알을 낳고 죽는다.

그 알은 40년째에 부화되어 1번 종로 그렘린이 나온다. 이 그렘린의 조상의 수는 3이다.

예제 입력 3

3 8
4 5
1 2 3 2
1 2 1 3
1 1
3
1
2 1
1 2
2 1

예제 출력 3

4
W3sicHJvYmxlbV9pZCI6IjI4OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI4MThcdWI5YjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWRmOFx1YjgxOFx1YjliMFx1Yzc0MCBcdWM3OTFcdWFjZTAsIFx1YzdhY1x1YmJmOFx1Yzc4OFx1YWNlMCwgXHVkMTM4XHVjNzc0IFx1YmNmNFx1YzFhMVx1YmNmNFx1YzFhMVx1ZDU1YyBcdWMwYzFcdWMwYzEgXHVjMThkXHVjNzU4IFx1YzY5NFx1YzgxNVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViODE4XHViOWIwXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1YjI5NCBOXHVhYzAwXHVjOWMwXHVjNzc0XHViYTcwLCBcdWQzYjhcdWM3NThcdWMwYzEmbmJzcDtcdWM4ODVcdWI5NThcdWJjYzRcdWI4NWMgMVx1YmM4OCBcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+VFx1YjE0NCBcdWM4MDQgXHVkNTVjIFx1YzVmMFx1YWQ2Y1x1YzE4Y1x1YzVkMFx1YzExYyBcdWQzZWRcdWJjMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4IE4gXHVjODg1XHViOTU4XHVjNzU4IFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc3NCBcdWQ1NWMgXHViOWM4XHViOWFjXHVjNTI5IFx1YzBkZFx1YWNhOFx1YjBhY1x1YjJlNC4gXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIFx1YjQ1MCBcdWIyZThcdWFjYzRcdWM3NTggXHVjMTMxXHVjN2E1IFx1YWNmY1x1YzgxNShcdWM1NGMmbmJzcDsmcmFycjsgXHVjMTMxXHVjN2E1XHVhZTMwKVx1Yzc0NCBcdWM5YzBcdWIwOTggXHVjNjQ0XHVjODA0XHVkNzg4IFx1Yzc5MFx1Yjc4MFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODg1XHViOTU4XHVhYzAwIGlcdWM3NzggXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIFx1YzU0Y1x1YzVkMFx1YzExYyBcdWJkODBcdWQ2NTRcdWQ1NThcdWFjZTAgWWlcdWIxNDQgXHViM2Q5XHVjNTQ4IFx1YzEzMVx1YzdhNVx1YWUzMFx1Yjk3YyBcdWM5YzBcdWIwOWNcdWIyZTQuIFx1YzEzMVx1YzdhNVx1Yzc0NCBcdWM2NDRcdWM4MDRcdWQ3ODggXHViOWM4XHVjZTVjIFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc0MCBcdWM2NDRcdWM4MDRcdWQ1NWMgXHVjMTMxXHVjN2E1IFx1YzljMVx1ZDZjNCBLaVx1YWMxY1x1Yzc1OCBcdWM1NGNcdWM3NDQgXHViMGIzXHViMjk0XHViMmU0LiBcdWFjMDEgXHVjNTRjIFx1YmNjNFx1Yjg1YyBcdWQwZGNcdWM1YjRcdWIwOThcdWIyOTQgXHVhZGY4XHViODE4XHViOWIwIFx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWIyZTRcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjNTRjXHVjNzc0IFx1YmQ4MFx1ZDY1NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHViM2M0IFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIFx1YzU0Y1x1Yzc0NCBcdWIyZTQgXHViMGIzXHVhY2UwIFx1YzhmZFx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2VkXHViYzFjXHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjA5OFx1YWNlMCZuYnNwO1RcdWIxNDRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDYwNFx1YzdhYywgXHVhY2ZjXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YzVlY1x1ZDBkY1x1YWU0Y1x1YzljMCBcdWM4NzRcdWM3YWNcdWQ1ODhcdWIzNTgmbmJzcDtcdWFkZjhcdWI4MThcdWI5YjAgXHVjOTExXHVjNWQwIFx1Yzg3MFx1YzBjMVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwJm5ic3A7XHVhZGY4XHViODE4XHViOWIwXHVjNzc0IFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHViMmU0XHViOWNjIFx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWM1NDRcdWM5YzEgXHViZDgwXHVkNjU0XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NDAgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1Yzg3MFx1YzBjMVx1Yzc3NFx1Yjc4MCwgXHViZDgwXHViYWE4LCBcdWJkODBcdWJhYThcdWM3NTggXHViZDgwXHViYWE4LCBcdWJkODBcdWJhYThcdWM3NTggXHViZDgwXHViYWE4XHVjNzU4IFx1YmQ4MFx1YmFhOCwgLi4uIFx1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NWNcdWIyZTQuIFx1YzYyY1x1ZDU3NCBcdWJkODBcdWQ2NTQgXHVjNjA4XHVjODE1XHVjNzc4IFx1YzU0Y1x1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHViZDgwXHVkNjU0XHViNDE4XHVjNWM4XHViMmU0XHVhY2UwIFx1YmQxMFx1YjNjNCBcdWJiMzRcdWJjMjlcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWIzYzRcdWM2NDAgXHVhYzAwXHVjN2E1IFx1Yzg3MFx1YzBjMVx1Yzc3NCBcdWI5Y2VcdWM3NDAgXHVhZGY4XHViODE4XHViOWIwXHVjNzU4IFx1Yzg3MFx1YzBjMVx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViODE4XHViOWIwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWQzZWRcdWJjMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDljIFx1YjRhNCBcdWM5YzBcdWIwOWMgXHViMTQ0IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLCAxICZsZTsgVCAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAzTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViODE4XHViOWIwIFx1Yzg4NVx1Yjk1OFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBLPHN1Yj5pPFwvc3ViPlx1YzY0MCBZPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBLPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAsIDEgJmxlOyBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIEs8c3ViPmk8XC9zdWI+XHViMjk0IFx1YmQ4MFx1ZDY1NFx1ZDU1OFx1YjI5NCBcdWM1NGNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwLCBZPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4IFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViZDgwXHVkNjU0XHVkNTVjIFx1YjRhNCBcdWMxMzFcdWM3YTVcdWFlMzBcdWI5N2MgXHVhYzcwXHVjZTU4XHViMjk0IFx1YWUzMFx1YWMwNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzU0Y1x1Yzc3NCBcdWJkODBcdWQ2NTRcdWI0MThcdWFjZTAgXHViMDk4XHVjNjI0XHViMjk0IFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc1OCBcdWM4ODVcdWI5NThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0Jm5ic3A7S2lcdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNTRjXHVjNzc0IFx1YmQ4MFx1ZDY1NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHViMTQ0IFx1YzIxOFx1YWMwMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IDFcdWM3NzRcdWMwYzEgMTAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVhYzEyXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjODcwXHVjMGMxXHVjNzc0IFx1YjljZVx1Yzc0MCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NTggXHVjODcwXHVjMGMxXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPjJcdWJjODggXHVjODg1XHViOTU4IFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc3NCBcdWQzZWRcdWJjMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDljIFx1YjRhNCA1XHViMTQ0XHVjOWY4XHVjNWQwIFx1YzU0Y1x1Yzc0NCBcdWIwYjNcdWFjZTAgXHVjOGZkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNTRjXHVjNzQwIDEwXHViMTQ0XHVjOWY4XHVjNWQwIFx1YmQ4MFx1ZDY1NFx1YjQxOFx1YzViNCAxXHViYzg4IFx1Yzg4NVx1Yjk1OCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIDIwXHViMTQ0XHVjOWY4XHVjNWQwIFx1YzU0Y1x1Yzc0NCBcdWIwYjNcdWFjZTAgXHVjOGZkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNTRjXHVjNzQwIDI1XHViMTQ0XHVjOWY4XHVjNWQwIFx1YmQ4MFx1ZDY1NFx1YjQxOFx1YzViNCAxXHViYzg4IFx1Yzg4NVx1Yjk1OCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIDM1XHViMTQ0XHVjOWY4XHVjNWQwIFx1YzU0Y1x1Yzc0NCBcdWIwYjNcdWFjZTAgXHVjOGZkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNTRjXHVjNzQwIDQwXHViMTQ0XHVjOWY4XHVjNWQwIFx1YmQ4MFx1ZDY1NFx1YjQxOFx1YzViNCAxXHViYzg4IFx1Yzg4NVx1Yjg1YyBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzU4IFx1Yzg3MFx1YzBjMVx1Yzc1OCBcdWMyMThcdWIyOTQgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIyODk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR1JFTUxJTkkiLCJkZXNjcmlwdGlvbiI6IjxwPkdyZW1saW5zIGFyZSBzbWFsbCwgZnVubnksIGZ1enp5IGNyZWF0dXJlcy4gSW4gdGltZXMgbG9uZyBnb25lIHRoZXkgdXNlZCB0byBjYXVzZSBxdWl0ZSBhIHJ1Y2t1cywgYnV0IG5vdyBtb3N0IG9mIHRoZW0gbGl2ZSBkZWNlbnQsIGhvbmVzdCBmYW1pbHkgbGl2ZXMuPFwvcD5cclxuXHJcbjxwPlRoZXJlIGFyZSBOIGRpZmZlcmVudCB0eXBlcyBvZiBncmVtbGlucywgY29kZWQgd2l0aCBudW1iZXJzIDEgdG8gTiBmb3IgeW91ciBjb252ZW5pZW5jZS4gTGVnZW5kIGhhcyBpdCB0aGF0IFQgeWVhcnMgYWdvIGEgbGFib3JhdG9yeSBhY2NpZGVudCBvY2N1cnJlZCBjYXVzaW5nIE4gZ3JlbWxpbnMsIG9uZSBvZiBlYWNoIHR5cGUgdG8gYmUgYm9ybi48XC9wPlxyXG5cclxuPHA+QXMgeW91IGFsbCBrbm93LCBpbiBvcmRlciBmb3IgZ3JlbWxpbnMgdG8gcmVwcm9kdWNlLCBubyBtYXRpbmcgcml0dWFscyBhcmUgcmVxdWlyZWQuIEp1c3QgYWRkIGEgZGFzaCBvZiB3YXR0ZXIgYW5kIHlvdSBpbnN0YW50bHkgZ2V0IGEgZmV3IG5ldyBjb2Nvb25zLjxcL3A+XHJcblxyXG48cD5HcmVtbGlucyBvZiB0eXBlIGkgbmVlZCBleGFjdGx5IFlpIHllYXJzIHRvIG1hdHVyZSBhbmQgc3Bhd24gS2kgY29jb29ucy4gRm9yIGVhY2ggY29jb29uIHlvdSBrbm93IGhvdyBtdWNoIHllYXJzIGRvZXMgaXQgdGFrZSB0byBoYXRjaCwgYW5kIHdoaWNoIGdyZW1saW4gdHlwZSBpcyBjb250YWluZWQgd2l0aGluLiBUaGUgb3JpZ2luYWwgZ3JlbWxpbiB1bmZvcnR1bmF0ZWx5IGRpZXMgd2hpbGUgcHJvZHVjaW5nIGNvY29vbnMuPFwvcD5cclxuXHJcbjxwPk5vdywgVCB5ZWFycyBhZnRlciB0aGUgb3JpZ2luYWwgYWNjaWRlbnQuIFNjaWVudGlzdCB3b25kZXIgd2hhdCBpcyB0aGUgbG9uZ2VzdCBhbmNlc3RyYWwgY2hhaW4gd2hvc2UgZ2Vub21lIGlzIGN1cnJlbnRseSByZXByZXNlbnRlZC4gVGhleSBhcmUgb25seSBpbnRlcmVzdGVkIGluIGFuY2VzdG9ycyBvZiBoYXRjaGVkIGdyZW1saW5zLCBub3QgdGhvc2Ugc3RpbGwgY29jb29uZWQuIFlvdSBhcmUgc2FmZSB0byBhc3N1bWUgdGhhdCBhbGwgZ3JlbWxpbnMgdGhhdCB3ZXJlIHN1cHBvc2VkIHRvIGhhdGNoIHRoaXMgeWVhciBkaWQgc28uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgVCAoMSAmbGU7IE4gJmxlOyAxMDAsIDEgJmxlOyBUICZsZTsgMTA8c3VwPjE1PFwvc3VwPiksIG51bWJlciBvZiBncmVtbGluIHR5cGVzIGFuZCBudW1iZXIgb2YgeWVhcnMgYWZ0ZXIgdGhlIG9yaWdpbmFsIGFjY2lkZW50LjxcL3A+XHJcblxyXG48cD5OZXh0IDNcdTIyMTlOIGxpbmVzIGNvbnRhaW4gZ3JlbWxpbiB0eXBlIGRlc2NyaXB0aW9ucywgdGhyZWUgbGluZXMgcGVyIHR5cGU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Rmlyc3QgbGluZSBjb250YWlucyBpbnRlZ2VycyBLPHN1Yj5pPFwvc3ViPiBhbmQgWTxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBLPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAsIDEgJmxlOyBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApLCBudW1iZXIgb2YgY29jb29ucyBmb3JtZWQgd2hlbiB0aGlzIGdyZW1saW4gdHlwZSBzcGF3bnMgYW5kIG51bWJlciBvZiB5ZWFycyB0aGlzIGdyZW1saW4gdHlwZSBuZWVkcyB0byByZWFjaCBtYXR1cml0eS48XC9saT5cclxuXHQ8bGk+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIEs8c3ViPmk8XC9zdWI+IGludGVnZXJzIGJldHdlZW4gMSBhbmQgTiBpbmNsdXNpdmUsIHR5cGVzIG9mIGdyZW1saW5zIGhhdGNoZWQgZnJvbSBjb2Nvb25zIGZvcm1lZCBieSB0aGlzIGdyZW1saW4gdHlwZS48XC9saT5cclxuXHQ8bGk+VGhlIHRoaXJkIGxpbmUgY29udGFpbnMgSzxzdWI+aTxcL3N1Yj4gaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCAxMDAwLCByZXByZXNlbnRpbmcgaGF0Y2hpbmcgdGltZSBmb3IgZWFjaCBjb2Nvb24sIGluIHllYXJzLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBsZW5ndGggb2YgdGhlIGN1cnJlbnRseSBsb25nZXN0IGFuY2VzdHJhbCBjaGFpbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBvcmlnaW5hbCBncmVtbGluIGhhdGNoZWQgaW4gdGhlIGFjY2lkZW50IGFmdGVyIDEwIHllYXJzIHNwYXducyBhIHNpbmdsZSBjb2Nvb24gYW5kIGRpZXMuPFwvcD5cclxuXHJcbjxwPjE1IHllYXJzIGFmdGVyIHRoZSBhY2NpZGVudCwgYSBuZXcgZ3JlbWxpbiBoYXRjaGVzIGZyb20gdGhlIGNvY29vbi4gSGlzIGFuY2VzdHJhbCBjaGFpbiBjb250YWlucyBvbmUgZ3JlbWxpbi4gMjUgeWVhcnMgYWZ0ZXIgdGhlIGFjY2lkZW50IHRoaXMgZ3JlbWxpbiBzcGF3bnMgYSBuZXcgY29jb29uIGFuZCBkaWVzLjxcL3A+XHJcblxyXG48cD4zMCB5ZWFycyBhZnRlciB0aGUgYWNjaWRlbnQsIGEgbmV3IGdyZW1saW4gaGF0Y2hlcyBmcm9tIHRoZSBjb2Nvb24uIEhpcyBhbmNlc3RyYWwgY2hhaW4gY29udGFpbnMgdHdvIGdyZW1saW5zLiA0MCB5ZWFycyBhZnRlciB0aGUgYWNjaWRlbnQgdGhpcyBncmVtbGluIHNwYXducyBhIG5ldyBjb2Nvb24gYW5kIGRpZXMuPFwvcD5cclxuXHJcbjxwPjQyIHllYXJzIGFmdGVyIHRoZSBhY2NpZGVudCwgdGhlIGN1cnJlbnQgY29jb29uIGlzIG5vdCB5ZXQgaGF0Y2hlZCwgc28gdGhlIGxvbmdlc3QgYW5jZXN0cmFsIGNoYWluIGV2ZXIgcmVjb3JkZWQgaXMgdHdvIGdyZW1saW5zIGluIGxlbmd0aC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+VGhlIG9yaWdpbmFsIGdyZW1saW4gaGF0Y2hlZCBpbiB0aGUgYWNjaWRlbnQgYWZ0ZXIgMTAgeWVhcnMgc3Bhd25zIGEgc2luZ2xlIGNvY29vbiBhbmQgZGllcy48XC9wPlxyXG5cclxuPHA+MTUgeWVhcnMgYWZ0ZXIgdGhlIGFjY2lkZW50LCBhIG5ldyBncmVtbGluIGhhdGNoZXMgZnJvbSB0aGUgY29jb29uLiBIaXMgYW5jZXN0cmFsIGNoYWluIGNvbnRhaW5zIG9uZSBncmVtbGluLiAyNSB5ZWFycyBhZnRlciB0aGUgYWNjaWRlbnQgdGhpcyBncmVtbGluIHNwYXducyBhIG5ldyBjb2Nvb24gYW5kIGRpZXMuPFwvcD5cclxuXHJcbjxwPjMwIHllYXJzIGFmdGVyIHRoZSBhY2NpZGVudCwgYSBuZXcgZ3JlbWxpbiBoYXRjaGVzIGZyb20gdGhlIGNvY29vbi4gSGlzIGFuY2VzdHJhbCBjaGFpbiBjb250YWlucyB0d28gZ3JlbWxpbnMuIDQwIHllYXJzIGFmdGVyIHRoZSBhY2NpZGVudCB0aGlzIGdyZW1saW4gc3Bhd25zIGEgbmV3IGNvY29vbiBhbmQgZGllcy48XC9wPlxyXG5cclxuPHA+NDIgeWVhcnMgYWZ0ZXIgdGhlIGFjY2lkZW50LCB0aGUgY3VycmVudCBjb2Nvb24gaXMgbm90IHlldCBoYXRjaGVkLCBzbyB0aGUgbG9uZ2VzdCBhbmNlc3RyYWwgY2hhaW4gZXZlciByZWNvcmRlZCBpcyB0d28gZ3JlbWxpbnMgaW4gbGVuZ3RoLjxcL3A+XHJcbiJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #6 6번