시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 8 8 50.000%

문제

그렘린은 작고, 재미있고, 털이 보송보송한 상상 속의 요정이다. 그렘린의 종류는 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

2 42
1 10
1
5
1 5
1
5

예제 출력 1

3

힌트

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

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

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

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

W3sicHJvYmxlbV9pZCI6IjI4OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkZjhcdWI4MThcdWI5YjAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWRmOFx1YjgxOFx1YjliMFx1Yzc0MCBcdWM3OTFcdWFjZTAsIFx1YzdhY1x1YmJmOFx1Yzc4OFx1YWNlMCwgXHVkMTM4XHVjNzc0IFx1YmNmNFx1YzFhMVx1YmNmNFx1YzFhMVx1ZDU1YyBcdWMwYzFcdWMwYzEgXHVjMThkXHVjNzU4IFx1YzY5NFx1YzgxNVx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViODE4XHViOWIwXHVjNzU4IFx1Yzg4NVx1Yjk1OFx1YjI5NCBOXHVhYzAwXHVjOWMwXHVjNzc0XHViYTcwLCBcdWQzYjhcdWM3NThcdWMwYzEmbmJzcDtcdWM4ODVcdWI5NThcdWJjYzRcdWI4NWMgMVx1YmM4OCBcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+VFx1YjE0NCBcdWM4MDQgXHVkNTVjIFx1YzVmMFx1YWQ2Y1x1YzE4Y1x1YzVkMFx1YzExYyBcdWQzZWRcdWJjMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4IE4gXHVjODg1XHViOTU4XHVjNzU4IFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc3NCBcdWQ1NWMgXHViOWM4XHViOWFjXHVjNTI5IFx1YzBkZFx1YWNhOFx1YjBhY1x1YjJlNC4gXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIFx1YjQ1MCBcdWIyZThcdWFjYzRcdWM3NTggXHVjMTMxXHVjN2E1IFx1YWNmY1x1YzgxNShcdWM1NGMmbmJzcDsmcmFycjsgXHVjMTMxXHVjN2E1XHVhZTMwKVx1Yzc0NCBcdWM5YzBcdWIwOTggXHVjNjQ0XHVjODA0XHVkNzg4IFx1Yzc5MFx1Yjc4MFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODg1XHViOTU4XHVhYzAwIGlcdWM3NzggXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIFx1YzU0Y1x1YzVkMFx1YzExYyBcdWJkODBcdWQ2NTRcdWQ1NThcdWFjZTAgWWlcdWIxNDQgXHViM2Q5XHVjNTQ4IFx1YzEzMVx1YzdhNVx1YWUzMFx1Yjk3YyBcdWM5YzBcdWIwOWNcdWIyZTQuIFx1YzEzMVx1YzdhNVx1Yzc0NCBcdWM2NDRcdWM4MDRcdWQ3ODggXHViOWM4XHVjZTVjIFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc0MCBcdWM2NDRcdWM4MDRcdWQ1NWMgXHVjMTMxXHVjN2E1IFx1YzljMVx1ZDZjNCBLaVx1YWMxY1x1Yzc1OCBcdWM1NGNcdWM3NDQgXHViMGIzXHViMjk0XHViMmU0LiBcdWFjMDEgXHVjNTRjIFx1YmNjNFx1Yjg1YyBcdWQwZGNcdWM1YjRcdWIwOThcdWIyOTQgXHVhZGY4XHViODE4XHViOWIwIFx1Yzg4NVx1Yjk1OFx1YWMwMCBcdWIyZTRcdWI5N2MgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjNTRjXHVjNzc0IFx1YmQ4MFx1ZDY1NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHViM2M0IFx1YjJlNFx1Yjk3YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIFx1YzU0Y1x1Yzc0NCBcdWIyZTQgXHViMGIzXHVhY2UwIFx1YzhmZFx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2VkXHViYzFjXHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjA5OFx1YWNlMCZuYnNwO1RcdWIxNDRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDYwNFx1YzdhYywgXHVhY2ZjXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YzVlY1x1ZDBkY1x1YWU0Y1x1YzljMCBcdWM4NzRcdWM3YWNcdWQ1ODhcdWIzNTgmbmJzcDtcdWFkZjhcdWI4MThcdWI5YjAgXHVjOTExXHVjNWQwIFx1Yzg3MFx1YzBjMVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwJm5ic3A7XHVhZGY4XHViODE4XHViOWIwXHVjNzc0IFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHViMmU0XHViOWNjIFx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWM1NDRcdWM5YzEgXHViZDgwXHVkNjU0XHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NDAgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1Yzg3MFx1YzBjMVx1Yzc3NFx1Yjc4MCwgXHViZDgwXHViYWE4LCBcdWJkODBcdWJhYThcdWM3NTggXHViZDgwXHViYWE4LCBcdWJkODBcdWJhYThcdWM3NTggXHViZDgwXHViYWE4XHVjNzU4IFx1YmQ4MFx1YmFhOCwgLi4uIFx1YjljYyBcdWFjZTBcdWI4MjRcdWQ1NWNcdWIyZTQuIFx1YzYyY1x1ZDU3NCBcdWJkODBcdWQ2NTQgXHVjNjA4XHVjODE1XHVjNzc4IFx1YzU0Y1x1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHViZDgwXHVkNjU0XHViNDE4XHVjNWM4XHViMmU0XHVhY2UwIFx1YmQxMFx1YjNjNCBcdWJiMzRcdWJjMjlcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWIzYzRcdWM2NDAgXHVhYzAwXHVjN2E1IFx1Yzg3MFx1YzBjMVx1Yzc3NCBcdWI5Y2VcdWM3NDAgXHVhZGY4XHViODE4XHViOWIwXHVjNzU4IFx1Yzg3MFx1YzBjMVx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViODE4XHViOWIwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWQzZWRcdWJjMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDljIFx1YjRhNCBcdWM5YzBcdWIwOWMgXHViMTQ0IFx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLCAxICZsZTsgVCAmbGU7IDEwPHN1cD4xNTxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAzTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhZGY4XHViODE4XHViOWIwIFx1Yzg4NVx1Yjk1OFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBLPHN1Yj5pPFwvc3ViPlx1YzY0MCBZPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDEgJmxlOyBLPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDAsIDEgJmxlOyBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIEs8c3ViPmk8XC9zdWI+XHViMjk0IFx1YmQ4MFx1ZDY1NFx1ZDU1OFx1YjI5NCBcdWM1NGNcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHVhY2UwLCBZPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4IFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViZDgwXHVkNjU0XHVkNTVjIFx1YjRhNCBcdWMxMzFcdWM3YTVcdWFlMzBcdWI5N2MgXHVhYzcwXHVjZTU4XHViMjk0IFx1YWUzMFx1YWMwNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzU0Y1x1Yzc3NCBcdWJkODBcdWQ2NTRcdWI0MThcdWFjZTAgXHViMDk4XHVjNjI0XHViMjk0IFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc1OCBcdWM4ODVcdWI5NThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0Jm5ic3A7S2lcdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjNTRjXHVjNzc0IFx1YmQ4MFx1ZDY1NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHViMTQ0IFx1YzIxOFx1YWMwMCZuYnNwO1x1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IDFcdWM3NzRcdWMwYzEgMTAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVhYzEyXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVjODcwXHVjMGMxXHVjNzc0IFx1YjljZVx1Yzc0MCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NTggXHVjODcwXHVjMGMxXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjJcdWJjODggXHVjODg1XHViOTU4IFx1YWRmOFx1YjgxOFx1YjliMFx1Yzc3NCBcdWQzZWRcdWJjMWNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDljIFx1YjRhNCA1XHViMTQ0XHVjOWY4XHVjNWQwIFx1YzU0Y1x1Yzc0NCBcdWIwYjNcdWFjZTAgXHVjOGZkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNTRjXHVjNzQwIDEwXHViMTQ0XHVjOWY4XHVjNWQwIFx1YmQ4MFx1ZDY1NFx1YjQxOFx1YzViNCAxXHViYzg4IFx1Yzg4NVx1Yjk1OCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIDIwXHViMTQ0XHVjOWY4XHVjNWQwIFx1YzU0Y1x1Yzc0NCBcdWIwYjNcdWFjZTAgXHVjOGZkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNTRjXHVjNzQwIDI1XHViMTQ0XHVjOWY4XHVjNWQwIFx1YmQ4MFx1ZDY1NFx1YjQxOFx1YzViNCAxXHViYzg4IFx1Yzg4NVx1Yjk1OCBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzQwIDM1XHViMTQ0XHVjOWY4XHVjNWQwIFx1YzU0Y1x1Yzc0NCBcdWIwYjNcdWFjZTAgXHVjOGZkXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNTRjXHVjNzQwIDQwXHViMTQ0XHVjOWY4XHVjNWQwIFx1YmQ4MFx1ZDY1NFx1YjQxOFx1YzViNCAxXHViYzg4IFx1Yzg4NVx1Yjg1YyBcdWFkZjhcdWI4MThcdWI5YjBcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViODE4XHViOWIwXHVjNzU4IFx1Yzg3MFx1YzBjMVx1Yzc1OCBcdWMyMThcdWIyOTQgM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHUkVNTElOSSIsImRlc2NyaXB0aW9uIjoiPHA+R3JlbWxpbnMgYXJlIHNtYWxsLCBmdW5ueSwgZnV6enkgY3JlYXR1cmVzLiBJbiB0aW1lcyBsb25nIGdvbmUgdGhleSB1c2VkIHRvIGNhdXNlIHF1aXRlIGEgcnVja3VzLCBidXQgbm93IG1vc3Qgb2YgdGhlbSBsaXZlIGRlY2VudCwgaG9uZXN0IGZhbWlseSBsaXZlcy48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIE4gZGlmZmVyZW50IHR5cGVzIG9mIGdyZW1saW5zLCBjb2RlZCB3aXRoIG51bWJlcnMgMSB0byBOIGZvciB5b3VyIGNvbnZlbmllbmNlLiBMZWdlbmQgaGFzIGl0IHRoYXQgVCB5ZWFycyBhZ28gYSBsYWJvcmF0b3J5IGFjY2lkZW50IG9jY3VycmVkIGNhdXNpbmcgTiBncmVtbGlucywgb25lIG9mIGVhY2ggdHlwZSB0byBiZSBib3JuLjxcL3A+XHJcblxyXG48cD5BcyB5b3UgYWxsIGtub3csIGluIG9yZGVyIGZvciBncmVtbGlucyB0byByZXByb2R1Y2UsIG5vIG1hdGluZyByaXR1YWxzIGFyZSByZXF1aXJlZC4gSnVzdCBhZGQgYSBkYXNoIG9mIHdhdHRlciBhbmQgeW91IGluc3RhbnRseSBnZXQgYSBmZXcgbmV3IGNvY29vbnMuPFwvcD5cclxuXHJcbjxwPkdyZW1saW5zIG9mIHR5cGUgaSBuZWVkIGV4YWN0bHkgWWkgeWVhcnMgdG8gbWF0dXJlIGFuZCBzcGF3biBLaSBjb2Nvb25zLiBGb3IgZWFjaCBjb2Nvb24geW91IGtub3cgaG93IG11Y2ggeWVhcnMgZG9lcyBpdCB0YWtlIHRvIGhhdGNoLCBhbmQgd2hpY2ggZ3JlbWxpbiB0eXBlIGlzIGNvbnRhaW5lZCB3aXRoaW4uIFRoZSBvcmlnaW5hbCBncmVtbGluIHVuZm9ydHVuYXRlbHkgZGllcyB3aGlsZSBwcm9kdWNpbmcgY29jb29ucy48XC9wPlxyXG5cclxuPHA+Tm93LCBUIHllYXJzIGFmdGVyIHRoZSBvcmlnaW5hbCBhY2NpZGVudC4gU2NpZW50aXN0IHdvbmRlciB3aGF0IGlzIHRoZSBsb25nZXN0IGFuY2VzdHJhbCBjaGFpbiB3aG9zZSBnZW5vbWUgaXMgY3VycmVudGx5IHJlcHJlc2VudGVkLiBUaGV5IGFyZSBvbmx5IGludGVyZXN0ZWQgaW4gYW5jZXN0b3JzIG9mIGhhdGNoZWQgZ3JlbWxpbnMsIG5vdCB0aG9zZSBzdGlsbCBjb2Nvb25lZC4gWW91IGFyZSBzYWZlIHRvIGFzc3VtZSB0aGF0IGFsbCBncmVtbGlucyB0aGF0IHdlcmUgc3VwcG9zZWQgdG8gaGF0Y2ggdGhpcyB5ZWFyIGRpZCBzby48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBUICgxICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IFQgJmxlOyAxMDxzdXA+MTU8XC9zdXA+KSwgbnVtYmVyIG9mIGdyZW1saW4gdHlwZXMgYW5kIG51bWJlciBvZiB5ZWFycyBhZnRlciB0aGUgb3JpZ2luYWwgYWNjaWRlbnQuPFwvcD5cclxuXHJcbjxwPk5leHQgM1x1MjIxOU4gbGluZXMgY29udGFpbiBncmVtbGluIHR5cGUgZGVzY3JpcHRpb25zLCB0aHJlZSBsaW5lcyBwZXIgdHlwZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5GaXJzdCBsaW5lIGNvbnRhaW5zIGludGVnZXJzIEs8c3ViPmk8XC9zdWI+IGFuZCBZPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IEs8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMCwgMSAmbGU7IFk8c3ViPmk8XC9zdWI+ICZsZTsgMTAwMCksIG51bWJlciBvZiBjb2Nvb25zIGZvcm1lZCB3aGVuIHRoaXMgZ3JlbWxpbiB0eXBlIHNwYXducyBhbmQgbnVtYmVyIG9mIHllYXJzIHRoaXMgZ3JlbWxpbiB0eXBlIG5lZWRzIHRvIHJlYWNoIG1hdHVyaXR5LjxcL2xpPlxyXG5cdDxsaT5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgSzxzdWI+aTxcL3N1Yj4gaW50ZWdlcnMgYmV0d2VlbiAxIGFuZCBOIGluY2x1c2l2ZSwgdHlwZXMgb2YgZ3JlbWxpbnMgaGF0Y2hlZCBmcm9tIGNvY29vbnMgZm9ybWVkIGJ5IHRoaXMgZ3JlbWxpbiB0eXBlLjxcL2xpPlxyXG5cdDxsaT5UaGUgdGhpcmQgbGluZSBjb250YWlucyBLPHN1Yj5pPFwvc3ViPiBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIDEwMDAsIHJlcHJlc2VudGluZyBoYXRjaGluZyB0aW1lIGZvciBlYWNoIGNvY29vbiwgaW4geWVhcnMuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGxlbmd0aCBvZiB0aGUgY3VycmVudGx5IGxvbmdlc3QgYW5jZXN0cmFsIGNoYWluLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIG9yaWdpbmFsIGdyZW1saW4gaGF0Y2hlZCBpbiB0aGUgYWNjaWRlbnQgYWZ0ZXIgMTAgeWVhcnMgc3Bhd25zIGEgc2luZ2xlIGNvY29vbiBhbmQgZGllcy48XC9wPlxyXG5cclxuPHA+MTUgeWVhcnMgYWZ0ZXIgdGhlIGFjY2lkZW50LCBhIG5ldyBncmVtbGluIGhhdGNoZXMgZnJvbSB0aGUgY29jb29uLiBIaXMgYW5jZXN0cmFsIGNoYWluIGNvbnRhaW5zIG9uZSBncmVtbGluLiAyNSB5ZWFycyBhZnRlciB0aGUgYWNjaWRlbnQgdGhpcyBncmVtbGluIHNwYXducyBhIG5ldyBjb2Nvb24gYW5kIGRpZXMuPFwvcD5cclxuXHJcbjxwPjMwIHllYXJzIGFmdGVyIHRoZSBhY2NpZGVudCwgYSBuZXcgZ3JlbWxpbiBoYXRjaGVzIGZyb20gdGhlIGNvY29vbi4gSGlzIGFuY2VzdHJhbCBjaGFpbiBjb250YWlucyB0d28gZ3JlbWxpbnMuIDQwIHllYXJzIGFmdGVyIHRoZSBhY2NpZGVudCB0aGlzIGdyZW1saW4gc3Bhd25zIGEgbmV3IGNvY29vbiBhbmQgZGllcy48XC9wPlxyXG5cclxuPHA+NDIgeWVhcnMgYWZ0ZXIgdGhlIGFjY2lkZW50LCB0aGUgY3VycmVudCBjb2Nvb24gaXMgbm90IHlldCBoYXRjaGVkLCBzbyB0aGUgbG9uZ2VzdCBhbmNlc3RyYWwgY2hhaW4gZXZlciByZWNvcmRlZCBpcyB0d28gZ3JlbWxpbnMgaW4gbGVuZ3RoLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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