시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17996 4910 3138 26.584%

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최대값을 출력한다.

예제 입력 1

4 7
20 15 10 17

예제 출력 1

15
W3sicHJvYmxlbV9pZCI6IjI4MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0IE1cdWJiZjhcdWQxMzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZmNcdWNjOThcdWM1ZDAgXHViMDk4XHViYjM0XHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU2MCBcdWFjZjNcdWM3NzQgXHViYWE4XHViNDUwIFx1YjlkZFx1ZDU3NFx1YmM4NFx1YjgzOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzgxNVx1YmQ4MFx1YzVkMCBcdWJjOGNcdWJhYTkgXHVkNWM4XHVhYzAwXHViOTdjIFx1YzY5NFx1Y2NhZFx1ZDU4OFx1YjJlNC4gXHVjODE1XHViZDgwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWM5ZDEgXHVhZGZjXHVjYzk4XHVjNzU4IFx1YjA5OFx1YmIzNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWJjOGNcdWJhYTkgXHVkNWM4XHVhYzAwXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1YyBcdWFkNmNcdWM3ODVcdWQ1NWMgXHViYWE5XHVjN2FjXHVjODA4XHViMmU4XHVhZTMwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWIwOThcdWJiMzRcdWI5N2MgXHVhZDZjXHVkNTYwXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYTlcdWM3YWNcdWM4MDhcdWIyZThcdWFlMzBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWIzZDlcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YmEzY1x1YzgwMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgwOFx1YjJlOFx1YWUzMFx1YzVkMCBcdWIxOTJcdWM3NzQgSFx1Yjk3YyBcdWM5YzBcdWM4MTVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIxOTJcdWM3NzRcdWI5N2MgXHVjOWMwXHVjODE1XHVkNTU4XHViYTc0IFx1ZDFiMVx1YjBhMFx1Yzc3NCBcdWI1NDVcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgSFx1YmJmOFx1ZDEzMCBcdWM3MDRcdWI4NWMgXHVjNjJjXHViNzdjXHVhYzA0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzVmMFx1YzE4ZFx1ZDU3NFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWI5N2MgXHViYWE4XHViNDUwIFx1YzgwOFx1YjJlOFx1ZDU3NFx1YmM4NFx1YjliMFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWIxOTJcdWM3NzRcdWFjMDAgSFx1YmNmNFx1YjJlNCBcdWQwNzAgXHViMDk4XHViYjM0XHViMjk0IEggXHVjNzA0XHVjNzU4IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWM3OThcdWI5YjQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWIwYWVcdWM3NDAgXHViMDk4XHViYjM0XHViMjk0IFx1Yzc5OFx1YjlhY1x1YzljMCBcdWM1NGFcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YzVmMFx1YzE4ZFx1ZDU3NFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIDIwLCAxNSwgMTAsIDE3XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjE5Mlx1Yzc3NFx1Yjk3YyAxNVx1Yjg1YyBcdWM5YzBcdWM4MTVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM3OTBcdWI5NzggXHViNGE0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCAxNSwgMTUsIDEwLCAxNVx1YWMwMCBcdWI0MjAgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIDVcdWM3NzggXHViMDk4XHViYjM0XHVjNjQwIDJcdWM3NzggXHViMDk4XHViYjM0XHViOTdjIFx1YjRlNFx1YWNlMCBcdWM5ZDFcdWM1ZDAgXHVhYzA4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gKFx1Y2QxZCA3XHViYmY4XHVkMTMwXHViOTdjIFx1YzlkMVx1YzVkMCBcdWI0ZTRcdWFjZTAgXHVhYzA0XHViMmU0KTxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNjU4XHVhY2JkXHVjNWQwIFx1YjllNFx1YzZiMCBcdWFkMDBcdWMyZWNcdWM3NzQgXHViOWNlXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViMDk4XHViYjM0XHViOTdjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWI5Y2NcdWQwN2NcdWI5Y2MgXHVjOWQxXHVjNzNjXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YzgwMVx1YzViNFx1YjNjNCBNXHViYmY4XHVkMTMwXHVjNzU4IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM5ZDFcdWM1ZDAgXHVhYzAwXHVjODM4XHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM4MDhcdWIyZThcdWFlMzBcdWM1ZDAgXHVjMTI0XHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMTkyXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMDk4XHViYjM0XHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHVjODM4XHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVhZTM4XHVjNzc0IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDAsIDEgJmxlOyBNICZsZTsgMiwwMDAsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMDk4XHViYjM0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVkNTZkXHVjMGMxIE1cdWM3NDQgXHViMTE4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzlkMVx1YzVkMCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMDk4XHViYjM0XHViOTdjIFx1ZDU2ZFx1YzBjMSBcdWFjMDBcdWM4MzhcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViMTkyXHVjNzc0XHViMjk0IDEsMDAwLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IFx1YjYxMFx1YjI5NCAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzgwMVx1YzViNFx1YjNjNCBNXHViYmY4XHVkMTMwXHVjNzU4IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM5ZDFcdWM1ZDAgXHVhYzAwXHVjODM4XHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM4MDhcdWIyZThcdWFlMzBcdWM1ZDAgXHVjMTI0XHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMTkyXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVLTyIsImRlc2NyaXB0aW9uIjoiPHA+THVtYmVyamFjayBNaXJrbyBuZWVkcyB0byBjaG9wIGRvd24gTSBtZXRyZXMgb2Ygd29vZC4gSXQgaXMgYW4gZWFzeSBqb2IgZm9yIGhpbSBzaW5jZSBoZSBoYXMgYSBuaWZ0eSBuZXcgd29vZGN1dHRpbmcgbWFjaGluZSB0aGF0IGNhbiB0YWtlIGRvd24gZm9yZXN0cyBsaWtlIHdpbGRmaXJlLiBIb3dldmVyLCBNaXJrbyBpcyBvbmx5IGFsbG93ZWQgdG8gY3V0IGEgc2luZ2xlIHJvdyBvZiB0cmVlcy48XC9wPlxyXG5cclxuPHA+TWlya29cdTIwMWZzIG1hY2hpbmUgd29ya3MgYXMgZm9sbG93czogTWlya28gc2V0cyBhIGhlaWdodCBwYXJhbWV0ZXIgSCAoaW4gbWV0cmVzKSwgYW5kIHRoZSBtYWNoaW5lIHJhaXNlcyBhIGdpYW50IHNhd2JsYWRlIHRvIHRoYXQgaGVpZ2h0IGFuZCBjdXRzIG9mZiBhbGwgdHJlZSBwYXJ0cyBoaWdoZXIgdGhhbiBIIChvZiBjb3Vyc2UsIHRyZWVzIG5vdCBoaWdoZXIgdGhhbiBIIG1ldGVycyByZW1haW4gaW50YWN0KS4gTWlya28gdGhlbiB0YWtlcyB0aGUgcGFydHMgdGhhdCB3ZXJlIGN1dCBvZmYuIEZvciBleGFtcGxlLCBpZiB0aGUgdHJlZSByb3cgY29udGFpbnMgdHJlZXMgd2l0aCBoZWlnaHRzIG9mIDIwLCAxNSwgMTAsIGFuZCAxNyBtZXRyZXMsIGFuZCBNaXJrbyByYWlzZXMgaGlzIHNhd2JsYWRlIHRvIDE1IG1ldHJlcywgdGhlIHJlbWFpbmluZyB0cmVlIGhlaWdodHMgYWZ0ZXIgY3V0dGluZyB3aWxsIGJlIDE1LCAxNSwgMTAsIGFuZCAxNSBtZXRyZXMsIHJlc3BlY3RpdmVseSwgd2hpbGUgTWlya28gd2lsbCB0YWtlIDUgbWV0cmVzIG9mZiB0aGUgZmlyc3QgdHJlZSBhbmQgMiBtZXRyZXMgb2ZmIHRoZSBmb3VydGggdHJlZSAoNyBtZXRyZXMgb2Ygd29vZCBpbiB0b3RhbCkuPFwvcD5cclxuXHJcbjxwPk1pcmtvIGlzIGVjb2xvZ2ljYWxseSBtaW5kZWQsIHNvIGhlIGRvZXNuXHUyMDFmdCB3YW50IHRvIGN1dCBvZmYgbW9yZSB3b29kIHRoYW4gbmVjZXNzYXJ5LiBUaGF0XHUyMDFmcyB3aHkgaGUgd2FudHMgdG8gc2V0IGhpcyBzYXdibGFkZSBhcyBoaWdoIGFzIHBvc3NpYmxlLiBIZWxwIE1pcmtvIGZpbmQgdGhlIG1heGltdW0gaW50ZWdlciBoZWlnaHQgb2YgdGhlIHNhd2JsYWRlIHRoYXQgc3RpbGwgYWxsb3dzIGhpbSB0byBjdXQgb2ZmIGF0IGxlYXN0IE0gbWV0cmVzIG9mIHdvb2QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzLCBOICh0aGUgbnVtYmVyIG9mIHRyZWVzLCAxICZsZTsgTiAmbGU7IDEgMDAwIDAwMCkgYW5kIE0gKE1pcmtvXHUyMDFmcyByZXF1aXJlZCB3b29kIGFtb3VudCwgMSAmbGU7IE0gJmxlOyAyIDAwMCAwMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiAxIDAwMCAwMDAgMDAwLCB0aGUgaGVpZ2h0cyBvZiBlYWNoIHRyZWUgKGluIG1ldHJlcykuIFRoZSBzdW0gb2YgYWxsIGhlaWdodHMgd2lsbCBleGNlZWQgTSwgdGh1cyBNaXJrbyB3aWxsIGFsd2F5cyBiZSBhYmxlIHRvIG9idGFpbiB0aGUgcmVxdWlyZWQgYW1vdW50IG9mIHdvb2QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgaGVpZ2h0IHNldHRpbmcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 2번