문제
NLCS Jeju에서는 학생회(Student Council) 회장 강준석이 다른 학생 단체에 예산을 분배한다.
준석이는 학생회를 제외한 $N$개의 단체에 올해 예산 $M$을 분배해야 한다. $N$개의 단체에 예산을 분배하고 남은 금액을 학생회 예산으로 사용할 수 있다. 준석이는 학생회 예산으로 최대한 많은 예산을 가져오고 싶어 어떻게 예산을 분배할지 깊은 고민에 빠졌다.
매년 예산 분배가 끝난 직후 학생 단체들은 학생회장을 탄핵할지 투표를 진행한다. $i$번째 학생단체는 $V_i$표를 투표할 수 있다. 투표 결과 탄핵에 찬성하는 표가 과반인 경우 학생회장이 탄핵된다.
각 학생단체는 학생회보다 더 많은 예산을 받기를 원한다. 학생회보다 많거나 같은 예산을 받은 학생단체는 학생회장을 탄핵하는데 반대로 투표하며, 학생회보다 적은 예산을 받은 학생단체는 학생회장을 탄핵하는 데 투표할 것이다.
준석이가 학생회로 예산을 아무리 많이 가져온다고 한들 탄핵되면 아무 의미가 없어진다. 준석이는 탄핵되지 않으면서 학생회로 최대한 예산을 가져오려고 한다.
모든 학생 단체에 0ドル$ 이상의 예산을 분배하고 남은 예산이 학생회의 예산이 된다. 준석이가 탄핵되지 않으면서 가져올 수 있는 최대 예산을 구해보자.
출력
준석이가 탄핵되지 않으면서 학생회가 가져갈 수 있는 최대 예산을 정수로 출력한다.
제한
- 1ドル \le N \le 100,000円$
- 1ドル \le M \le 10^9$
- 1ドル \le V_i \le 10^9$
W3sicHJvYmxlbV9pZCI6IjMxNjczIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMmI5XHViY2M0XHVkNTVjIFx1ZDU1OVx1YzBkZFx1ZDY4Y1x1YzdhNSBcdWFkNTBcdWNjYjQiLCJkZXNjcmlwdGlvbiI6IjxwPk5MQ1MgSmVqdVx1YzVkMFx1YzExY1x1YjI5NCBcdWQ1NTlcdWMwZGRcdWQ2OGMoU3R1ZGVudCBDb3VuY2lsKSBcdWQ2OGNcdWM3YTUgXHVhYzE1XHVjOTAwXHVjMTFkXHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWQ1NTlcdWMwZGQgXHViMmU4XHVjY2I0XHVjNWQwIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWJkODRcdWJjMzBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzkwMFx1YzExZFx1Yzc3NFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWQ2OGNcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjICROJFx1YWMxY1x1Yzc1OCBcdWIyZThcdWNjYjRcdWM1ZDAgXHVjNjJjXHVkNTc0IFx1YzYwOFx1YzBiMCAkTSRcdWM3NDQgXHViZDg0XHViYzMwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gJE4kXHVhYzFjXHVjNzU4IFx1YjJlOFx1Y2NiNFx1YzVkMCBcdWM2MDhcdWMwYjBcdWM3NDQgXHViZDg0XHViYzMwXHVkNTU4XHVhY2UwIFx1YjBhOFx1Yzc0MCBcdWFlMDhcdWM1NjFcdWM3NDQgXHVkNTU5XHVjMGRkXHVkNjhjIFx1YzYwOFx1YzBiMFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOTAwXHVjMTFkXHVjNzc0XHViMjk0IFx1ZDU1OVx1YzBkZFx1ZDY4YyBcdWM2MDhcdWMwYjBcdWM3M2NcdWI4NWMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc0MCBcdWM2MDhcdWMwYjBcdWM3NDQgXHVhYzAwXHVjODM4XHVjNjI0XHVhY2UwIFx1YzJmNlx1YzViNCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNjA4XHVjMGIwXHVjNzQ0IFx1YmQ4NFx1YmMzMFx1ZDU2MFx1YzljMCBcdWFlNGFcdWM3NDAgXHVhY2UwXHViYmZjXHVjNWQwIFx1YmU2MFx1Yzg0Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0XHViMTQ0IFx1YzYwOFx1YzBiMCBcdWJkODRcdWJjMzBcdWFjMDAgXHViMDVkXHViMDljIFx1YzljMVx1ZDZjNCBcdWQ1NTlcdWMwZGQgXHViMmU4XHVjY2I0XHViNGU0XHVjNzQwIFx1ZDU1OVx1YzBkZFx1ZDY4Y1x1YzdhNVx1Yzc0NCBcdWQwYzRcdWQ1NzVcdWQ1NjBcdWM5YzAgXHVkMjJjXHVkNDVjXHViOTdjIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1ZDU1OVx1YzBkZFx1YjJlOFx1Y2NiNFx1YjI5NCAkVl9pJFx1ZDQ1Y1x1Yjk3YyBcdWQyMmNcdWQ0NWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkMjJjXHVkNDVjIFx1YWNiMFx1YWNmYyBcdWQwYzRcdWQ1NzVcdWM1ZDAgXHVjYzJjXHVjMTMxXHVkNTU4XHViMjk0IFx1ZDQ1Y1x1YWMwMCBcdWFjZmNcdWJjMThcdWM3NzggXHVhY2JkXHVjNmIwIFx1ZDU1OVx1YzBkZFx1ZDY4Y1x1YzdhNVx1Yzc3NCBcdWQwYzRcdWQ1NzVcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQ1NTlcdWMwZGRcdWIyZThcdWNjYjRcdWIyOTQgXHVkNTU5XHVjMGRkXHVkNjhjXHViY2Y0XHViMmU0IFx1YjM1NCBcdWI5Y2VcdWM3NDAgXHVjNjA4XHVjMGIwXHVjNzQ0IFx1YmMxYlx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NWNcdWIyZTQuIFx1ZDU1OVx1YzBkZFx1ZDY4Y1x1YmNmNFx1YjJlNCBcdWI5Y2VcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWJjMWJcdWM3NDAgXHVkNTU5XHVjMGRkXHViMmU4XHVjY2I0XHViMjk0IFx1ZDU1OVx1YzBkZFx1ZDY4Y1x1YzdhNVx1Yzc0NCBcdWQwYzRcdWQ1NzVcdWQ1NThcdWIyOTRcdWIzNzAgXHViYzE4XHViMzAwXHViODVjIFx1ZDIyY1x1ZDQ1Y1x1ZDU1OFx1YmE3MCwgXHVkNTU5XHVjMGRkXHVkNjhjXHViY2Y0XHViMmU0IFx1YzgwMVx1Yzc0MCBcdWM2MDhcdWMwYjBcdWM3NDQgXHViYzFiXHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjJlOFx1Y2NiNFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWQ2OGNcdWM3YTVcdWM3NDQgXHVkMGM0XHVkNTc1XHVkNTU4XHViMjk0IFx1YjM3MCBcdWQyMmNcdWQ0NWNcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWMxMWRcdWM3NzRcdWFjMDAgXHVkNTU5XHVjMGRkXHVkNjhjXHViODVjIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWM1NDRcdWJiMzRcdWI5YWMgXHViOWNlXHVjNzc0IFx1YWMwMFx1YzgzOFx1YzYyOFx1YjJlNFx1YWNlMCBcdWQ1NWNcdWI0ZTQgXHVkMGM0XHVkNTc1XHViNDE4XHViYTc0IFx1YzU0NFx1YmIzNCBcdWM3NThcdWJiZjhcdWFjMDAgXHVjNWM2XHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5MDBcdWMxMWRcdWM3NzRcdWIyOTQgXHVkMGM0XHVkNTc1XHViNDE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBcdWQ1NTlcdWMwZGRcdWQ2OGNcdWI4NWMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWFjMDBcdWM4MzhcdWM2MjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkNTU5XHVjMGRkIFx1YjJlOFx1Y2NiNFx1YzVkMCAkMCQgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWJkODRcdWJjMzBcdWQ1NThcdWFjZTAgXHViMGE4XHVjNzQwIFx1YzYwOFx1YzBiMFx1Yzc3NCBcdWQ1NTlcdWMwZGRcdWQ2OGNcdWM3NTggXHVjNjA4XHVjMGIwXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjOTAwXHVjMTFkXHVjNzc0XHVhYzAwIFx1ZDBjNFx1ZDU3NVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVhYzAwXHVjODM4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWIyZThcdWNjYjRcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWNkMWRcdWM2MDhcdWMwYjBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCAkTSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWIyZThcdWNjYjRcdWFjMDAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNDVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkVl9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM5MDBcdWMxMWRcdWM3NzRcdWFjMDAgXHVkMGM0XHVkNTc1XHViNDE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NFx1YzExYyBcdWQ1NTlcdWMwZGRcdWQ2OGNcdWFjMDAgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzYwOFx1YzBiMFx1Yzc0NCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAxMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgTSBcXGxlIDEwXjkkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgVl9pIFxcbGUgMTBeOSQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjMxNjczIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXhjZXB0aW9uYWwgU3R1ZGVudCBDb3VuY2lsIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBOTENTIEplanUsIHRoZSBIZWFkIG9mIHRoZSBTdHVkZW50IENvdW5jaWwmbmJzcDtBYXJlbiBLYW5nIGRpc3RyaWJ1dGVzIHRoZSBidWRnZXQgdG8gb3RoZXIgc3R1ZGVudCBvcmdhbmlzYXRpb25zLjxcL3A+XHJcblxyXG48cD5BYXJlbiBtdXN0IGRpc3RyaWJ1dGUgdGhlIHRvdGFsIGJ1ZGdldCAkTSQgdG8gJE4kIG90aGVyIG9yZ2FuaXNhdGlvbnMsIGV4Y2x1ZGluZyB0aGUgU3R1ZGVudCBDb3VuY2lsLiBUaGUgcmVtYWluaW5nIGFtb3VudCBhZnRlciBkaXN0cmlidXRpb24gdG8gJE4kIG9yZ2FuaXNhdGlvbnMgY2FuIGJlIHVzZWQgYXMgdGhlIFN0dWRlbnQgQ291bmNpbCYjMzk7cyBidWRnZXQuIEFhcmVuIHdhbnRzIHRvIGJyaW5nIGFzIG11Y2ggYnVkZ2V0IGFzIHBvc3NpYmxlIHRvIHRoZSBTdHVkZW50IENvdW5jaWwgYW5kIGlzIGZpbmRpbmcgYSB3YXkgdG8gZGlzdHJpYnV0ZSB0aGUgYnVkZ2V0LjxcL3A+XHJcblxyXG48cD5FdmVyeSB5ZWFyLCByaWdodCBhZnRlciB0aGUgYnVkZ2V0IGRpc3RyaWJ1dGlvbiBpcyBjb21wbGV0ZWQsIHRoZSBzdHVkZW50IG9yZ2FuaXNhdGlvbnMgdm90ZSBvbiB3aGV0aGVyIHRvIGltcGVhY2ggdGhlIFN0dWRlbnQgQ291bmNpbCBQcmVzaWRlbnQuIFRoZSAkaSQtdGggc3R1ZGVudCBvcmdhbmlzYXRpb24gY2FuIGNhc3QmbmJzcDskVl9pJCB2b3Rlcy4gSWYgdGhlIG1ham9yaXR5IHZvdGVzIGluIGZhdm91ciwgdGhlIFN0dWRlbnQgQ291bmNpbCBQcmVzaWRlbnQgd2lsbCBiZSBpbXBlYWNoZWQuPFwvcD5cclxuXHJcbjxwPkVhY2ggc3R1ZGVudCBvcmdhbmlzYXRpb24gd2FudHMgdG8gcmVjZWl2ZSBtb3JlIGJ1ZGdldCB0aGFuIHRoZSBTdHVkZW50IENvdW5jaWwuIE9yZ2FuaXNhdGlvbnMgdGhhdCByZWNlaXZlIHRoZSBzYW1lIG9yIG1vcmUgYnVkZ2V0IHRoYW4gdGhlIFN0dWRlbnQgQ291bmNpbCB3aWxsIHZvdGUgYWdhaW5zdCBpbXBlYWNoaW5nIHRoZSBQcmVzaWRlbnQsIHdoaWxlIHRob3NlIHRoYXQgcmVjZWl2ZSBsZXNzIHdpbGwgdm90ZSBmb3IgaW1wZWFjaG1lbnQuPFwvcD5cclxuXHJcbjxwPkV2ZW4gaWYgQWFyZW4gYnJpbmdzIGFzIG11Y2ggYnVkZ2V0IGFzIHBvc3NpYmxlIHRvIHRoZSBTdHVkZW50IENvdW5jaWwsIGl0IHdpbGwgYmUgbWVhbmluZ2xlc3MgaWYgaGUgaXMgaW1wZWFjaGVkLiBIZSB3YW50cyB0byBicmluZyB0aGUgbWF4aW11bSBidWRnZXQgdG8gdGhlIFN0dWRlbnQgQ291bmNpbCB3aXRob3V0IGJlaW5nIGltcGVhY2hlZC48XC9wPlxyXG5cclxuPHA+VGhlIGJ1ZGdldCBjYW4gYmUgZGlzdHJpYnV0ZWQgYXMgbm9uLW5lZ2F0aXZlIGludGVnZXJzIGluY2x1ZGluZyAkMCQgdG8gYWxsIHN0dWRlbnQgb3JnYW5pc2F0aW9ucywgYW5kIHRoZSByZW1haW5pbmcgYnVkZ2V0IGFmdGVyIGRpc3RyaWJ1dGlvbiBiZWNvbWVzIHRoZSBTdHVkZW50IENvdW5jaWwmIzM5O3MgYnVkZ2V0LiBGaW5kIHRoZSBtYXhpbXVtIGJ1ZGdldCBBYXJlbiBjYW4gYnJpbmcgdG8gdGhlIFN0dWRlbnQgQ291bmNpbCB3aXRob3V0IGJlaW5nIGltcGVhY2hlZC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMmbmJzcDskTiQgYW5kJm5ic3A7JE0kICQtJCB0aGUgbnVtYmVyIG9mIHN0dWRlbnQgb3JnYW5pc2F0aW9ucyZuYnNwO2FuZCB0aGUgdG90YWwgYnVkZ2V0LCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyAkTiQgaW50ZWdlcnMgJFZfaSQgJC0kIHRoZSBudW1iZXIgb2Ygdm90ZXMgZWFjaCBzdHVkZW50IG9yZ2FuaXNhdGlvbiBjYW4gY2FzdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCBhIHNpbmdsZSBpbnRlZ2VyICQtJCB0aGUgbWF4aW11bSBidWRnZXQgdGhhdCB0aGUgU3R1ZGVudCBDb3VuY2lsIGNhbiBrZWVwIHdpdGhvdXQgQWFyZW4gZ2V0dGluZyBpbXBlYWNoZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlIE4gXFxsZSAxMDBcXCwwMDAkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgTSBcXGxlIDEwXjkkPFwvbGk+XHJcblx0PGxpPiQxIFxcbGUgVl9pIFxcbGUgMTBeOSQ8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==