시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 117 53 42 60.870%

문제

유니스트 컴퓨터공학과에 다니는 서윤이는 이번에 어떤 과목을 들을지 고민중이다. 학점을 잘 받을 수 있으면서도 중요한 과목을 듣고 싶은 서윤이는 모든 과목의 중요도와, 일정 이상의 학점을 받기 위해 필요한 공부시간을 다 적었다.

처음에는 모든 과목을 들으려고 했던 서윤이는 자신의 공부 시간에 한계가 있다는 것을 깨달았다. 그래서, 공부 시간의 한계를 초과하지 않으면서 과목의 중요도 합이 최대가 되도록 몇 개만 선택하여 수강하기로 마음먹었다.

중요도가 최대가 되도록 과목을 선택했을 때, 최대가 되는 중요도를 출력하는 프로그램을 작성하시오.

입력

첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 

이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 공백을 사이에 두고 주어진다. 

출력

얻을 수 있는 최대 중요도를 출력한다.

예제 입력 1

80 3
650 40
700 60
60 40

예제 출력 1

710
W3sicHJvYmxlbV9pZCI6IjE3ODQ1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjE4XHVhYzE1IFx1YWNmY1x1YmFhOSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzIwXHViMmM4XHVjMmE0XHVkMmI4IFx1Y2VmNFx1ZDRlOFx1ZDEzMFx1YWNmNVx1ZDU1OVx1YWNmY1x1YzVkMCBcdWIyZTRcdWIyYzhcdWIyOTQgXHVjMTFjXHVjNzI0XHVjNzc0XHViMjk0IFx1Yzc3NFx1YmM4OFx1YzVkMCBcdWM1YjRcdWI1YTQgXHVhY2ZjXHViYWE5XHVjNzQ0IFx1YjRlNFx1Yzc0NFx1YzljMCBcdWFjZTBcdWJiZmNcdWM5MTFcdWM3NzRcdWIyZTQuIFx1ZDU1OVx1YzgxMFx1Yzc0NCBcdWM3OTggXHViYzFiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzRcdWMxMWNcdWIzYzQgXHVjOTExXHVjNjk0XHVkNTVjIFx1YWNmY1x1YmFhOVx1Yzc0NCBcdWI0ZTNcdWFjZTAgXHVjMmY2XHVjNzQwIFx1YzExY1x1YzcyNFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2ZjXHViYWE5XHVjNzU4IFx1YzkxMVx1YzY5NFx1YjNjNFx1YzY0MCwgXHVjNzdjXHVjODE1IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQ1NTlcdWM4MTBcdWM3NDQgXHViYzFiXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVhY2Y1XHViZDgwXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YjJlNCBcdWM4MDFcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M5OFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2ZjXHViYWE5XHVjNzQ0IFx1YjRlNFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1ODhcdWIzNTggXHVjMTFjXHVjNzI0XHVjNzc0XHViMjk0Jm5ic3A7XHVjNzkwXHVjMmUwXHVjNzU4IFx1YWNmNVx1YmQ4MCBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVkNTVjXHVhY2M0XHVhYzAwIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZTY4XHViMmVjXHVjNTU4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMsJm5ic3A7XHVhY2Y1XHViZDgwIFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWQ1NWNcdWFjYzRcdWI5N2MgXHVjZDA4XHVhY2ZjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyZuYnNwO1x1YWNmY1x1YmFhOVx1Yzc1OCBcdWM5MTFcdWM2OTRcdWIzYzQgXHVkNTY5XHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHViYTg3IFx1YWMxY1x1YjljYyBcdWMxMjBcdWQwZGRcdWQ1NThcdWM1ZWMgXHVjMjE4XHVhYzE1XHVkNTU4XHVhZTMwXHViODVjIFx1YjljOFx1Yzc0Y1x1YmEzOVx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTExXHVjNjk0XHViM2M0XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVhY2ZjXHViYWE5XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMFx1YWMwMCBcdWI0MThcdWIyOTQgXHVjOTExXHVjNjk0XHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCZuYnNwO1x1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5MDRcdWM1ZDAgXHVjMTFjXHVjNzI0XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjZjVcdWJkODBcdWMyZGNcdWFjMDQgTiAoMSZuYnNwOyZsZTsgTiAmbGU7IDEwLDAwMCksIFx1YWNmY1x1YmFhOSBcdWMyMTggSyAoMSZuYnNwOyZsZTsgSyAmbGU7IDEsMDAwKVx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCZuYnNwO1x1YzkxMVx1YzY5NFx1YjNjNCBJICgxJm5ic3A7JmxlOyBJICZsZTsgMTAwLDAwMCksIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWFjZjVcdWJkODBcdWMyZGNcdWFjMDQgKDEmbmJzcDsmbGU7IFQgJmxlOyAxMCwwMDApXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjOTExXHVjNjk0XHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzg0NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvdXJzZSIsImRlc2NyaXB0aW9uIjoiPHA+U291eW9vbiB3aG8gaXMgaW4gVU5JU1QgY29tcHV0ZXIgc2NpZW5jZSBpcyB3b3JyaWVkIGZvciB3aGF0IHN1YmplY3QgdG8gY291cnNlLjxiciBcLz5cclxuU291eW9vbiB3YW50cyB0byBjb3Vyc2Ugc29tZSBpbXBvcnRhbnQgY291cnNlcyBhbmQgZ2V0IGdvb2QgZ3JhZGUsIHNvIHNoZSB3cm90ZSBpbXBvcnRhbmNlIGFuZCByZXF1aXJlZCB0aW1lIGZvciBnZXQgZ29vZCBncmFkZSBvZiBhbGwgY29tcHV0ZXIgc2NpZW5jZSBjb3Vyc2VzLjxiciBcLz5cclxuQXQgZmlyc3QsIFNvdXlvb24gZGVjaWRlZCB0byBjb3Vyc2UgYWxsIGNvbXB1dGVyIHNjaWVuY2UgY291cnNlcywgc2hlIHJlYWxpemVkIHRoYXQmbmJzcDt0aGVyZSBpcyBsaW1pdCB0aW1lIHRoYXQgc2hlIGNhbiBzdHVkeS4gV2hpbGUgdGhpbmtpbmcgd2hhdCB0byBkbywgZmluYWxseSwgc2hlIGRlY2lkZWQgdG8gY2hvb3NlIHN1YmplY3RzIHRoYXQgc3VtIG9mIGltcG9ydGFuY2Ugb2Ygc3ViamVjdCBpcyBtYXhpbXVtLCB3aGlsZSBzdW0gb2YgcmVxdWlyZWQgc3R1ZHkgdGltZSBvZiBzdWJqZWN0cyBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gbGltaXQgdGltZSBvZiBzdHVkeSB0aW1lLiBNYWtlIHRoZSBwcm9ncmFtIHRoYXQgb3V0cHV0IHBvc3NpYmxlIG1heGltdW0gaW1wb3J0YW5jZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIGZpcnN0IGxpbmUsIFNvdVlvb24mIzM5O3MgbWF4aW11bSBzdHVkeSB0aW1lICZuYnNwO04oMSZuYnNwOyZsZTsmbmJzcDtOICZsZTsmbmJzcDsxMCwwMDApICw8YnIgXC8+XHJcbnN1YmplY3QgbnVtYmVyICZuYnNwO0soMSZuYnNwOyZsZTsmbmJzcDsmbmJzcDtLICZsZTsgMSwwMDApIGlzIGdpdmVuLG9uZSBzcGFjZSB3aWxsIGJlIGdpdmVuIGJldHdlZW4gTiBhbmQgSy4mbmJzcDs8YnIgXC8+XHJcbkZyb20gc2Vjb25kIGxpbmUgdG8gSysxdGggbGluZSwgZWFjaCZuYnNwO2ltcG9ydGFuY2UgSSgxJm5ic3A7JmxlOyZuYnNwO0kgJm5ic3A7JmxlOyZuYnNwOzEwMCwwMDApLCByZXF1aXJlZCBzdHVkeSB0aW1lIFQoMSZuYnNwOyZsZTsmbmJzcDtUICZsZTsmbmJzcDsxMCwwMDApIGlzIGdpdmVuLCBvbmUgc3BhY2Ugd2lsbCBiZSBnaXZlbiBiZXR3ZWVuIEkgYW5kIFQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHBvc3NpYmxlIG1heGltdW0gaW1wb3J0YW5jZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=