시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 194 45 34 22.222%

문제

재현이는 초고층 건물인 "제2사과타워"를 짓기 위해 노동자들을 고용하고 있다. 1번부터 N번까지 총 N명의 노동자들이 지원했는데, i (1 <= i <= N)번째 노동자는 최저임금 Si를 가지고 있어 Si보다 크거나 같은 만큼의 임금을 받아야 하며, 또한 Qi라는 건설 자격증 레벨을 가지고 있다.

최근 정부에서는 건설 자격증을 활성화하기 위해서, 노동자들의 임금을 항상 자격증 레벨에 비례하기 지급하게 하는 규정을 만들었다. 만약 A라는 노동자의 자격증 레벨이 Qa이고, B라는 노동자의 자격증 레벨이 Qb라면, A의 임금은 Qa * k, B의 임금은 Qb * k가 되어야 한다. 노동자들에게 지급하는 임금은 정수가 아닌 실수 범위여도 무방하다.

재현이는 수중에 W달러를 가지고 있으며, 사실 재현이는 자격증에 대해서는 별로 관심이 없고 그저 건물을 빨리 짓고 싶기 때문에, 자격증 레벨과 상관없이 현재 자금 내에서 가장 많은 노동자들을 고용하고 싶어 한다. 만약 고용할 수 있는 노동자의 수가 같다면, 노동자들에게 최소 비용을 지급하는 고용 방안을 원하며, 노동자의 수와 비용이 같다면 어떤 방법이든지 상관 없다. 재현이를 도와, 고용할 수 있는 노동자의 최대 수와 그 때 고용해야 할 노동자를 구하여라.

입력

표준 입력으로부터 다음의 데이터를 읽어야 한다 :

  • 첫째 줄에는 N과 W가 주어진다.
  • 이후 N개 줄에 각 노동자의 정보가 주어진다. 이후 주어지는 정보의 i번째 줄에는 i번째 노동자의 최저임금 Si, 자격증 레벨 Qi가 주어진다.
  • 1 <= N <= 500,000 지원 노동자의 수
  • 1 <= Sk <= 20,000 노동자 k의 최저임금
  • 1 <= Qk <= 20,000 노동자 k의 자격증 레벨
  • 1 <= W <= 10,000,000,000 사용할 수 있는 돈의 양

출력

표준 출력에 최대로 고용할 수 있는 노동자의 수 H를 출력하며, 이후 H개의 줄에 고용하고 싶어하는 노동자들의 번호를 출력한다. 노동자들의 번호는 제각기 달라야 하며 순서는 어떤 순서여도 상관없다.

예제 입력 1

4 100
5 1000
10 100
8 10
20 1

예제 출력 1

2
2
3

예제 입력 2

3 4
1 2
1 3
1 3

예제 출력 2

3
1
2
3

예제 입력 3

3 40
10 1
10 2
10 3

예제 출력 3

2
2
3
W3sicHJvYmxlbV9pZCI6IjU0NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWM2YTkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzdhY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWNkMDhcdWFjZTBcdWNlMzUgXHVhYzc0XHViYjNjXHVjNzc4ICZxdW90O1x1YzgxYzJcdWMwYWNcdWFjZmNcdWQwYzBcdWM2Y2MmcXVvdDtcdWI5N2MgXHVjOWQzXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWI0ZTRcdWM3NDQgXHVhY2UwXHVjNmE5XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1Y2QxZCBOXHViYTg1XHVjNzU4IFx1YjE3OFx1YjNkOVx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM5YzBcdWM2ZDBcdWQ1ODhcdWIyOTRcdWIzNzAsIGkgKDEgJmx0Oz0gaSAmbHQ7PSBOKVx1YmM4OFx1YzlmOCBcdWIxNzhcdWIzZDlcdWM3OTBcdWIyOTQgXHVjZDVjXHVjODAwXHVjNzg0XHVhZTA4IFNpXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM1YjQgU2lcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWI5Y2NcdWQwN2NcdWM3NTggXHVjNzg0XHVhZTA4XHVjNzQ0IFx1YmMxYlx1YzU0NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1YjYxMFx1ZDU1YyBRaVx1Yjc3Y1x1YjI5NCBcdWFjNzRcdWMxMjQgXHVjNzkwXHVhY2E5XHVjOTlkIFx1YjgwOFx1YmNhOFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWFkZmMgXHVjODE1XHViZDgwXHVjNWQwXHVjMTFjXHViMjk0IFx1YWM3NFx1YzEyNCBcdWM3OTBcdWFjYTlcdWM5OWRcdWM3NDQgXHVkNjVjXHVjMTMxXHVkNjU0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYywgXHViMTc4XHViM2Q5XHVjNzkwXHViNGU0XHVjNzU4IFx1Yzc4NFx1YWUwOFx1Yzc0NCBcdWQ1NmRcdWMwYzEgXHVjNzkwXHVhY2E5XHVjOTlkIFx1YjgwOFx1YmNhOFx1YzVkMCBcdWJlNDRcdWI4NDBcdWQ1NThcdWFlMzAgXHVjOWMwXHVhZTA5XHVkNTU4XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWFkZGNcdWM4MTVcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWI5Y2NcdWM1N2QgQVx1Yjc3Y1x1YjI5NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjNzkwXHVhY2E5XHVjOTlkIFx1YjgwOFx1YmNhOFx1Yzc3NCBRYVx1Yzc3NFx1YWNlMCwgQlx1Yjc3Y1x1YjI5NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjNzkwXHVhY2E5XHVjOTlkIFx1YjgwOFx1YmNhOFx1Yzc3NCBRYlx1Yjc3Y1x1YmE3NCwgQVx1Yzc1OCBcdWM3ODRcdWFlMDhcdWM3NDAgUWEgKiBrLCBCXHVjNzU4IFx1Yzc4NFx1YWUwOFx1Yzc0MCBRYiAqIGtcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViMTc4XHViM2Q5XHVjNzkwXHViNGU0XHVjNWQwXHVhYzhjIFx1YzljMFx1YWUwOVx1ZDU1OFx1YjI5NCBcdWM3ODRcdWFlMDhcdWM3NDAgXHVjODE1XHVjMjE4XHVhYzAwIFx1YzU0NFx1YjJjYyBcdWMyZTRcdWMyMTggXHViYzk0XHVjNzA0XHVjNWVjXHViM2M0IFx1YmIzNFx1YmMyOVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1YzIxOFx1YzkxMVx1YzVkMCBXXHViMmVjXHViN2VjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzBhY1x1YzJlNCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNzkwXHVhY2E5XHVjOTlkXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWJjYzRcdWI4NWMgXHVhZDAwXHVjMmVjXHVjNzc0IFx1YzVjNlx1YWNlMCBcdWFkZjhcdWM4MDAgXHVhYzc0XHViYjNjXHVjNzQ0IFx1YmU2OFx1YjlhYyBcdWM5ZDNcdWFjZTAgXHVjMmY2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzkwXHVhY2E5XHVjOTlkIFx1YjgwOFx1YmNhOFx1YWNmYyBcdWMwYzFcdWFkMDBcdWM1YzZcdWM3NzQgXHVkNjA0XHVjN2FjIFx1Yzc5MFx1YWUwOCBcdWIwYjRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWIxNzhcdWIzZDlcdWM3OTBcdWI0ZTRcdWM3NDQgXHVhY2UwXHVjNmE5XHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNCBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjZTBcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YWMxOVx1YjJlNFx1YmE3NCwgXHViMTc4XHViM2Q5XHVjNzkwXHViNGU0XHVjNWQwXHVhYzhjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjOWMwXHVhZTA5XHVkNTU4XHViMjk0IFx1YWNlMFx1YzZhOSBcdWJjMjlcdWM1NDhcdWM3NDQgXHVjNmQwXHVkNTU4XHViYTcwLCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjMjE4XHVjNjQwIFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWFjMTlcdWIyZTRcdWJhNzQgXHVjNWI0XHViNWE0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjRlMFx1YzljMCBcdWMwYzFcdWFkMDAgXHVjNWM2XHViMmU0LiBcdWM3YWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwLCBcdWFjZTBcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjZDVjXHViMzAwIFx1YzIxOFx1YzY0MCBcdWFkZjggXHViNTRjIFx1YWNlMFx1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHViMTc4XHViM2Q5XHVjNzkwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDQ1Y1x1YzkwMCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHViMmU0XHVjNzRjXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWM3N2RcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0IDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IE5cdWFjZmMgV1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjMDEgXHViMTc4XHViM2Q5XHVjNzkwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjODE1XHViY2Y0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHViMTc4XHViM2Q5XHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YzgwMFx1Yzc4NFx1YWUwOCBTaSwgXHVjNzkwXHVhY2E5XHVjOTlkIFx1YjgwOFx1YmNhOCBRaVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gTiAmbHQ7PSA1MDAsMDAwIFx1YzljMFx1YzZkMCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjMjE4PFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gU2sgJmx0Oz0gMjAsMDAwIFx1YjE3OFx1YjNkOVx1Yzc5MCBrXHVjNzU4IFx1Y2Q1Y1x1YzgwMFx1Yzc4NFx1YWUwODxcL2xpPlxyXG5cdDxsaT4xICZsdDs9IFFrICZsdDs9IDIwLDAwMCBcdWIxNzhcdWIzZDlcdWM3OTAga1x1Yzc1OCBcdWM3OTBcdWFjYTlcdWM5OWQgXHViODA4XHViY2E4PFwvbGk+XHJcblx0PGxpPjEgJmx0Oz0gVyAmbHQ7PSAxMCwwMDAsMDAwLDAwMCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzYzhcdWM3NTggXHVjNTkxPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ0NWNcdWM5MDAgXHVjZDljXHViODI1XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWFjZTBcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWM3NTggXHVjMjE4IEhcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBcdWM3NzRcdWQ2YzQgSFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhY2UwXHVjNmE5XHVkNTU4XHVhY2UwIFx1YzJmNlx1YzViNFx1ZDU1OFx1YjI5NCBcdWIxNzhcdWIzZDlcdWM3OTBcdWI0ZTRcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMTc4XHViM2Q5XHVjNzkwXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWM4MWNcdWFjMDFcdWFlMzAgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU1OFx1YmE3MCBcdWMyMWNcdWMxMWNcdWIyOTQgXHVjNWI0XHViNWE0IFx1YzIxY1x1YzExY1x1YzVlY1x1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTQ2MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhpcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGhhdmUgdG8gaGlyZSB3b3JrZXJzIGZvciBhIGNvbnN0cnVjdGlvbiBwcm9qZWN0LiBUaGVyZSBhcmUgTiBjYW5kaWRhdGVzIGFwcGx5aW5nIGZvciB0aGUgam9iLCBudW1iZXJlZCBmcm9tIDEgdG8gTiBpbmNsdXNpdmUuIEVhY2ggY2FuZGlkYXRlIGsgcmVxdWlyZXMgdGhhdCBpZiBoZSBpcyBoaXJlZCwgaGUgbXVzdCBiZSBwYWlkIGF0IGxlYXN0IFNrIGRvbGxhcnMuIEFsc28sIGVhY2ggY2FuZGlkYXRlIGsgaGFzIGEgcXVhbGlmaWNhdGlvbiBsZXZlbCBRay4gVGhlIHJlZ3VsYXRpb25zIG9mIHRoZSBjb25zdHJ1Y3Rpb24gaW5kdXN0cnkgcmVxdWlyZSB0aGF0IHlvdSBwYXkgeW91ciB3b3JrZXJzIGluIHByb3BvcnRpb24gdG8gdGhlaXIgcXVhbGlmaWNhdGlvbiBsZXZlbCwgcmVsYXRpdmUgdG8gZWFjaCBvdGhlci4gRm9yIGV4YW1wbGUsIGlmIHlvdSBoaXJlIHR3byB3b3JrZXJzIEEgYW5kIEIsIGFuZCBRQSA9IDMgKiBRQiwgdGhlbiB5b3UgaGF2ZSB0byBwYXkgd29ya2VyIEEgZXhhY3RseSB0aHJlZSB0aW1lcyBhcyBtdWNoIGFzIHlvdSBwYXkgd29ya2VyIEIuIFlvdSBhcmUgYWxsb3dlZCB0byBwYXkgeW91ciB3b3JrZXJzIG5vbi1pbnRlZ2VyIGFtb3VudHMgb2YgbW9uZXkuIFRoaXMgZXZlbiBpbmNsdWRlcyBxdWFudGl0aWVzIHRoYXQgY2Fubm90IGJlIHdyaXR0ZW4gd2l0aCBhIGZpbml0ZSBudW1iZXIgb2YgZGlnaXRzIGluIGRlY2ltYWwgZm9ybSwgc3VjaCBhcyBhIHRoaXJkIG9yIGEgc2l4dGggb2YgYSBkb2xsYXIuPFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIFcgZG9sbGFycyBhdCBoYW5kIGFuZCB5b3Ugd2FudCB0byBoaXJlIGFzIG1hbnkgd29ya2VycyBhcyBwb3NzaWJsZS4gWW91IGRlY2lkZSB3aG9tIHRvIGhpcmUgYW5kIGhvdyBtdWNoIHRvIHBheSB0aGVtLCBidXQgeW91IGhhdmUgdG8gbWVldCB0aGUgbWluaW11bSBzYWxhcnkgcmVxdWlyZW1lbnRzIG9mIHRob3NlIHlvdSBjaG9vc2UgdG8gaGlyZSwgYW5kIHlvdSBoYXZlIHRvIG9iZXkgdGhlIGluZHVzdHJ5IHJlZ3VsYXRpb25zLiBZb3UgYWxzbyBoYXZlIHRvIGZpdCB3aXRoaW4geW91ciBidWRnZXQgb2YgVyBkb2xsYXJzLjxcL3A+XHJcblxyXG48cD5UaGUgbmF0dXJlIG9mIHlvdXIgcHJvamVjdCBpcyBzdWNoIHRoYXQgdGhlIHF1YWxpZmljYXRpb24gbGV2ZWwgaXMgY29tcGxldGVseSBpcnJlbGV2YW50LCBzbyB5b3UgYXJlIG9ubHkgaW50ZXJlc3RlZCBpbiBtYXhpbWl6aW5nIHRoZSBudW1iZXIgb2Ygd29ya2VycyB3aXRob3V0IHJlZ2FyZCB0byB0aGVpciBxdWFsaWZpY2F0aW9uIGxldmVsLiBIb3dldmVyLCBpZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIHdheSB0byBhY2hpZXZlIHRoaXMsIHRoZW4geW91IHdhbnQgdG8gc2VsZWN0IHRoZSBvbmUgd2hlcmUgdGhlIHRvdGFsIGFtb3VudCBvZiBtb25leSB5b3UgaGF2ZSB0byBwYXkgeW91ciB3b3JrZXJzIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLiBJbiBjYXNlIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUgd2F5IHRvIGFjaGlldmUgdGhpcywgdGhlbiB5b3UgYXJlIGluZGlmZmVyZW50IGFtb25nIHRoZXNlIHdheXMgYW5kIHlvdSB3b3VsZCBiZSBzYXRpc2ZpZWQgd2l0aCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgZGlmZmVyZW50IHNhbGFyeSByZXF1aXJlbWVudHMgYW5kIHF1YWxpZmljYXRpb24gbGV2ZWxzIG9mIHRoZSBjYW5kaWRhdGVzLCBhcyB3ZWxsIGFzIHRoZSBhbW91bnQgb2YgbW9uZXkgeW91IGhhdmUsIGRldGVybWluZXMgd2hpY2ggY2FuZGlkYXRlcyB5b3Ugc2hvdWxkIGhpcmUuIFlvdSBtdXN0IGhpcmUgYXMgbWFueSBvZiB0aGVtIGFzIHBvc3NpYmxlIGFuZCB5b3UgbXVzdCBkbyBzbyB3aXRoIGFzIGxpdHRsZSBtb25leSBhcyBwb3NzaWJsZSwgd2hpbGUgY29tcGx5aW5nIHdpdGggdGhlIGluZHVzdHJ5IHJlZ3VsYXRpb25zIHNwZWNpZmllZCBhYm92ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG1heGltdW0gdmFsdWUgb2YgVyBkb2VzIG5vdCBmaXQgaW4gMzIgYml0cy4gWW91IGhhdmUgdG8gdXNlIGEgNjQtYml0IGRhdGEgdHlwZSwgc3VjaCBhcyBsb25nIGxvbmcgaW4gQ1wvQysrIG9yIGludDY0IGluIFBhc2NhbCwgaW4gb3JkZXIgdG8gc3RvcmUgdGhlIHZhbHVlIG9mIFcgaW4gYSBzaW5nbGUgdmFyaWFibGUuIFBsZWFzZSBzZWUgdGhlIHRlY2huaWNhbCBpbmZvIHNoZWV0IGZvciBkZXRhaWxzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIG11c3QgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0IHRoZSBmb2xsb3dpbmcgZGF0YTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgTiBhbmQgVywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvbGk+XHJcblx0PGxpPlRoZSBuZXh0IE4gbGluZXMgZGVzY3JpYmUgdGhlIGNhbmRpZGF0ZXMsIG9uZSBjYW5kaWRhdGUgcGVyIGxpbmUuIFRoZSBrdGggb2YgdGhlc2UgbGluZXMgZGVzY3JpYmVzIGNhbmRpZGF0ZSBudW1iZXIgayBhbmQgaXQgY29udGFpbnMgdGhlIGludGVnZXJzIFNrIGFuZCBRaywgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDUwMCwwMDAgVGhlIG51bWJlciBvZiBjYW5kaWRhdGVzPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBTayAmbGU7IDIwLDAwMCBUaGUgbWluaW11bSBzYWxhcnkgcmVxdWlyZW1lbnQgb2YgY2FuZGlkYXRlIGs8XC9saT5cclxuXHQ8bGk+MSAmbGU7IFFrICZsZTsgMjAsMDAwIFRoZSBxdWFsaWZpY2F0aW9uIGxldmVsIG9mIGNhbmRpZGF0ZSBrPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBXICZsZTsgMTAsMDAwLDAwMCwwMDAgVGhlIGFtb3VudCBvZiBtb25leSBhdmFpbGFibGUgdG8geW91Jm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gbXVzdCB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQgdGhlIGZvbGxvd2luZyBkYXRhOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBmaXJzdCBsaW5lIG11c3QgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIEgsIHRoZSBudW1iZXIgb2Ygd29ya2VycyB0aGF0IHlvdSBoaXJlLjxcL2xpPlxyXG5cdDxsaT5UaGUgbmV4dCBIIGxpbmVzIG11c3QgbGlzdCB0aGUgaWRlbnRpZnlpbmcgbnVtYmVycyBvZiB0aGUgY2FuZGlkYXRlcyB5b3UgY2hvb3NlIHRvIGhpcmUgKGVhY2ggb2YgdGhlbSBhIGRpZmZlcmVudCBudW1iZXIgYmV0d2VlbiAxIGFuZCBOKSwgb25lIHBlciBsaW5lLCBpbiBhbnkgb3JkZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPHA+U2FtcGxlIDE8XC9wPlxyXG5cclxuPHA+VGhlIG9ubHkgY29tYmluYXRpb24gZm9yIHdoaWNoIHlvdSBjYW4gYWZmb3JkIHRvIGhpcmUgdHdvIHdvcmtlcnMgYW5kIHN0aWxsIG1lZXQgYWxsIHRoZSBjb25zdHJhaW50cyBpcyBpZiB5b3Ugc2VsZWN0IHdvcmtlcnMgMiBhbmQgMy4gWW91IGNhbiBwYXkgdGhlbSA4MCBhbmQgOCBkb2xsYXJzIHJlc3BlY3RpdmVseSBhbmQgdGh1cyBmaXQgaW4geW91ciBidWRnZXQgb2YgMTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TYW1wbGUgMjxcL3A+XHJcblxyXG48cD5IZXJlIHlvdSBjYW4gYWZmb3JkIHRvIGhpcmUgYWxsIHRocmVlIHdvcmtlcnMuIFlvdSBwYXkgMSBkb2xsYXIgdG8gd29ya2VyIDEgYW5kIDEuNTAgZG9sbGFycyBlYWNoIHRvIHdvcmtlcnMgMiBhbmQgMywgYW5kIHlvdSBtYW5hZ2UgdG8gaGlyZSBldmVyeW9uZSB3aXRoIHRoZSA0IGRvbGxhcnMgdGhhdCB5b3UgaGF2ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2FtcGxlIDM8XC9wPlxyXG5cclxuPHA+SGVyZSB5b3UgY2Fubm90IGFmZm9yZCB0byBoaXJlIGFsbCB0aHJlZSB3b3JrZXJzLCBhcyBpdCB3b3VsZCBjb3N0IHlvdSA2MCBkb2xsYXJzLCBidXQgeW91IGNhbiBhZmZvcmQgdG8gaGlyZSBhbnkgdHdvIG9mIHRoZW0uIFlvdSBjaG9vc2UgdG8gaGlyZSB3b3JrZXJzIDIgYW5kIDMgYmVjYXVzZSB0aGV5IHdvdWxkIGNvc3QgeW91IHRoZSBzbWFsbGVzdCBzdW0gb2YgbW9uZXksIGNvbXBhcmVkIHRvIHRoZSBvdGhlciB0d28td29ya2VyIGNvbWJpbmF0aW9ucy4gWW91IGNhbiBwYXkgMTAgZG9sbGFycyB0byB3b3JrZXIgMiBhbmQgMTUgZG9sbGFycyB0byB3b3JrZXIgMyBmb3IgYSB0b3RhbCBvZiAyNSBkb2xsYXJzLiBJZiB5b3Ugd2VyZSB0byBoaXJlIHdvcmtlcnMgMSBhbmQgMiB5b3Ugd291bGQgaGF2ZSB0byBwYXkgdGhlbSBhdCBsZWFzdCAxMCBhbmQgMjAgZG9sbGFycyByZXNwZWN0aXZlbHkuIElmIHlvdSB3ZXJlIHRvIGhpcmUgMSBhbmQgMywgdGhlbiB5b3Ugd291bGQgaGF2ZSB0byBwYXkgdGhlbSBhdCBsZWFzdCAxMCBhbmQgMzAgZG9sbGFycyByZXNwZWN0aXZlbHkuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 2009 2번

  • 문제를 번역한 사람: koosaga