시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB41615912736.705%

문제

농부 존과 그의 소들은 프리스비를 하며 놀고 있다. 베시가 프리스비를 던지자, 마크한테 갔고 결국 마크네 팀에게 프리스비가 넘어갔다! 마크의 키는 H이고(1 <= H <= 1,000,000,000), 마크 근처에 있는 베시네 팀원은 N명 있다 (2 <= N <= 20). 마크가 던지는 프리스비를 뺏기 위해서는 마크보다 키가 크거나 같아야한다. 소 여러 마리가 하나의 스택을 쌓아 키를 높여도 된다. 각 소 마다 키, 무게와, 힘이 정해져 있다. 소의 힘이란 소가 들 수 있는 무게를 말한다.

이러한 조건이 주어졌을 때, 베시는 그녀의 팀이 마크의 프리스비를 뺏을 수 있는지 궁금해졌다. 만약 가능하다면, 최대로 안정된 정도를 원한다. 여기서 안정된 정도란 쌓은 스택의 맨 위에 추가로 더 올릴 수 있는 무게를 의미한다.

입력

입력의 첫 줄에는 N과 H가 주어진다.

다음 N개의 줄에 각 소의 키, 무게, 힘이 주어진다. 입력으로 주어지는 모든 수는 10억보다 크지 않은 자연수이다.

출력

베시네 팀이 마크의 프리스비를 뺏을 수 있다면, 최대의 안정된 정도를 출력한다. 만약 뺏을 수 없다면, "Mark is too tall"를 출력한다. (따옴표 제외)

예제 입력 1

4 10
9 4 1
3 3 5
5 5 10
4 4 5

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjEwNjQ5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTA0XHViOWFjXHVjMmE0XHViZTQ0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVjODc0XHVhY2ZjIFx1YWRmOFx1Yzc1OCBcdWMxOGNcdWI0ZTRcdWM3NDAgXHVkNTA0XHViOWFjXHVjMmE0XHViZTQ0XHViOTdjIFx1ZDU1OFx1YmE3MCBcdWIxODBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWJjYTBcdWMyZGNcdWFjMDAgXHVkNTA0XHViOWFjXHVjMmE0XHViZTQ0XHViOTdjIFx1YjM1OFx1YzljMFx1Yzc5MCwgXHViOWM4XHVkMDZjXHVkNTVjXHVkMTRjIFx1YWMxNFx1YWNlMCBcdWFjYjBcdWFkNmQgXHViOWM4XHVkMDZjXHViMTI0IFx1ZDMwMFx1YzVkMFx1YWM4YyBcdWQ1MDRcdWI5YWNcdWMyYTRcdWJlNDRcdWFjMDAgXHViMTE4XHVjNWI0XHVhYzE0XHViMmU0ISBcdWI5YzhcdWQwNmNcdWM3NTggXHVkMGE0XHViMjk0IEhcdWM3NzRcdWFjZTAoMSAmbHQ7PSBIICZsdDs9IDEsMDAwLDAwMCwwMDApLCBcdWI5YzhcdWQwNmMgXHVhZGZjXHVjYzk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJjYTBcdWMyZGNcdWIxMjQgXHVkMzAwXHVjNmQwXHVjNzQwIE5cdWJhODUgXHVjNzg4XHViMmU0ICgyICZsdDs9IE4gJmx0Oz0gMjApLiBcdWI5YzhcdWQwNmNcdWFjMDAgXHViMzU4XHVjOWMwXHViMjk0IFx1ZDUwNFx1YjlhY1x1YzJhNFx1YmU0NFx1Yjk3YyBcdWJlOGZcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YjljOFx1ZDA2Y1x1YmNmNFx1YjJlNCBcdWQwYTRcdWFjMDAgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YzU0NFx1YzU3Y1x1ZDU1Y1x1YjJlNC4gXHVjMThjIFx1YzVlY1x1YjdlYyBcdWI5YzhcdWI5YWNcdWFjMDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzJhNFx1ZDBkZFx1Yzc0NCBcdWMzMTNcdWM1NDQgXHVkMGE0XHViOTdjIFx1YjE5Mlx1YzVlY1x1YjNjNCBcdWI0MWNcdWIyZTQuIFx1YWMwMSBcdWMxOGMgXHViOWM4XHViMmU0IFx1ZDBhNCwgXHViYjM0XHVhYzhjXHVjNjQwLCBcdWQ3OThcdWM3NzQgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMThjXHVjNzU4IFx1ZDc5OFx1Yzc3NFx1Yjc4MCBcdWMxOGNcdWFjMDAgXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM0XHVhYzhjXHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1Yzg3MFx1YWM3NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjYTBcdWMyZGNcdWIyOTQgXHVhZGY4XHViMTQwXHVjNzU4IFx1ZDMwMFx1Yzc3NCBcdWI5YzhcdWQwNmNcdWM3NTggXHVkNTA0XHViOWFjXHVjMmE0XHViZTQ0XHViOTdjIFx1YmU4Zlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgXHVjZDVjXHViMzAwXHViODVjIFx1YzU0OFx1YzgxNVx1YjQxYyBcdWM4MTVcdWIzYzRcdWI5N2MgXHVjNmQwXHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgXHVjNTQ4XHVjODE1XHViNDFjIFx1YzgxNVx1YjNjNFx1Yjc4MCBcdWMzMTNcdWM3NDAgXHVjMmE0XHVkMGRkXHVjNzU4IFx1YjllOCBcdWM3MDRcdWM1ZDAgXHVjZDk0XHVhYzAwXHViODVjIFx1YjM1NCBcdWM2MmNcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzRcdWFjOGNcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWNmYyBIXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWMxOGNcdWM3NTggXHVkMGE0LCBcdWJiMzRcdWFjOGMsIFx1ZDc5OFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCAxMFx1YzViNVx1YmNmNFx1YjJlNCBcdWQwNmNcdWM5YzAgXHVjNTRhXHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJjYTBcdWMyZGNcdWIxMjQgXHVkMzAwXHVjNzc0IFx1YjljOFx1ZDA2Y1x1Yzc1OCBcdWQ1MDRcdWI5YWNcdWMyYTRcdWJlNDRcdWI5N2MgXHViZThmXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWM1NDhcdWM4MTVcdWI0MWMgXHVjODE1XHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1YmU4Zlx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtNYXJrIGlzIHRvbyB0YWxsJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YjUzMFx1YzYzNFx1ZDQ1YyBcdWM4MWNcdWM2NzgpPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA2NDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHdWFyZCBNYXJrIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBhbmQgaGlzIGhlcmQgYXJlIHBsYXlpbmcgZnJpc2JlZS4gJm5ic3A7QmVzc2llIHRocm93cyB0aGUgZnJpc2JlZSBkb3duIHRoZSBmaWVsZCwgYnV0IGl0JiMzOTtzIGdvaW5nIHN0cmFpZ2h0IHRvIE1hcmsgdGhlIGZpZWxkIGhhbmQgb24gdGhlIG90aGVyIHRlYW0hICZuYnNwO01hcmsgaGFzIGhlaWdodCBIICgxICZsdDs9IEggJmx0Oz0gMSwwMDAsMDAwLDAwMCksIGJ1dCB0aGVyZSBhcmUgTiBjb3dzIG9uIEJlc3NpZSYjMzk7cyB0ZWFtIGdhdGhlcmVkIGFyb3VuZCBNYXJrICgyICZsdDs9IE4gJmx0Oz0gMjApLiBUaGV5IGNhbiBvbmx5IGNhdGNoIHRoZSBmcmlzYmVlIGlmIHRoZXkgY2FuIHN0YWNrIHVwIHRvIGJlIGF0IGxlYXN0IGFzIGhpZ2ggYXMgTWFyay4gJm5ic3A7RWFjaCBvZiB0aGUgTiBjb3dzIGhhcyBhIGhlaWdodCwgd2VpZ2h0LCBhbmQgc3RyZW5ndGguIEEgY293JiMzOTtzIHN0cmVuZ3RoIGluZGljYXRlcyB0aGUgbWF4aW11bSBhbW91bnQgb2YgdG90YWwgd2VpZ2h0IG9mIHRoZSBjb3dzIHRoYXQgY2FuIGJlIHN0YWNrZWQgYWJvdmUgaGVyLiAmbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlc2UgY29uc3RyYWludHMsIEJlc3NpZSB3YW50cyB0byBrbm93IGlmIGl0IGlzIHBvc3NpYmxlIGZvciBoZXIgdGVhbSB0byBidWlsZCBhIHRhbGwgZW5vdWdoIHN0YWNrIHRvIGNhdGNoIHRoZSBmcmlzYmVlLCBhbmQgaWYgc28sIHdoYXQgaXMgdGhlIG1heGltdW0gc2FmZXR5IGZhY3RvciBvZiBzdWNoIGEgc3RhY2suICZuYnNwO1RoZSBzYWZldHkgZmFjdG9yIG9mIGEgc3RhY2sgaXMgdGhlIGFtb3VudCBvZiB3ZWlnaHQgdGhhdCBjYW4gYmUgYWRkZWQgdG8gdGhlIHRvcCBvZiB0aGUgc3RhY2sgd2l0aG91dCBleGNlZWRpbmcgYW55IGNvdyYjMzk7cyBzdHJlbmd0aC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gYW5kIEguPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgb2YgaW5wdXQgZWFjaCBkZXNjcmliZSBhIGNvdywgZ2l2aW5nIGl0cyBoZWlnaHQsIHdlaWdodCwgYW5kIHN0cmVuZ3RoLiAmbmJzcDtBbGwgYXJlIHBvc2l0aXZlIGludGVnZXJzIGF0IG1vc3QgMSBiaWxsaW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIEJlc3NpZSYjMzk7cyB0ZWFtIGNhbiBidWlsZCBhIHN0YWNrIHRhbGwgZW5vdWdoIHRvIGNhdGNoIHRoZSBmcmlzYmVlLCBwbGVhc2Ugb3V0cHV0IHRoZSBtYXhpbXVtIGFjaGlldmFibGUgc2FmZXR5IGZhY3RvciBmb3Igc3VjaCBhIHN0YWNrLiBPdGhlcndpc2Ugb3V0cHV0ICZxdW90O01hcmsgaXMgdG9vIHRhbGwmcXVvdDsgKHdpdGhvdXQgdGhlIHF1b3RlcykuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2014-2015 Season > USACO December 2014 Contest > Gold 1번

  • 문제를 번역한 사람: myungwoo
  • 잘못된 번역을 찾은 사람: suhgyuho