시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 21036 5765 3629 26.267%

문제

상근이는 나무 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+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNjU4XHVhY2JkXHVjNWQwIFx1YjllNFx1YzZiMCBcdWFkMDBcdWMyZWNcdWM3NzQgXHViOWNlXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViMDk4XHViYjM0XHViOTdjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWI5Y2NcdWQwN2NcdWI5Y2MgXHVjOWQxXHVjNzNjXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjODAxXHVjNWI0XHViM2M0IE1cdWJiZjhcdWQxMzBcdWM3NTggXHViMDk4XHViYjM0XHViOTdjIFx1YzlkMVx1YzVkMCBcdWFjMDBcdWM4MzhcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzgwOFx1YjJlOFx1YWUzMFx1YzVkMCBcdWMxMjRcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIwOThcdWJiMzRcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFlMzhcdWM3NzQgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLDAwMCwgMSAmbGU7IE0gJmxlOyAyLDAwMCwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIwOThcdWJiMzRcdWM3NTggXHViMTkyXHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWQ1NmRcdWMwYzEgTVx1Yzc0NCBcdWIxMThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWQxXHVjNWQwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIwOThcdWJiMzRcdWI5N2MgXHVkNTZkXHVjMGMxIFx1YWMwMFx1YzgzOFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIxOTJcdWM3NzRcdWIyOTQgMSwwMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggXHViNjEwXHViMjk0IDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjODAxXHVjNWI0XHViM2M0IE1cdWJiZjhcdWQxMzBcdWM3NTggXHViMDk4XHViYjM0XHViOTdjIFx1YzlkMVx1YzVkMCBcdWFjMDBcdWM4MzhcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzgwOFx1YjJlOFx1YWUzMFx1YzVkMCBcdWMxMjRcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRUtPIiwiZGVzY3JpcHRpb24iOiI8cD5MdW1iZXJqYWNrIE1pcmtvIG5lZWRzIHRvIGNob3AgZG93biBNIG1ldHJlcyBvZiB3b29kLiBJdCBpcyBhbiBlYXN5IGpvYiBmb3IgaGltIHNpbmNlIGhlIGhhcyBhIG5pZnR5IG5ldyB3b29kY3V0dGluZyBtYWNoaW5lIHRoYXQgY2FuIHRha2UgZG93biBmb3Jlc3RzIGxpa2Ugd2lsZGZpcmUuIEhvd2V2ZXIsIE1pcmtvIGlzIG9ubHkgYWxsb3dlZCB0byBjdXQgYSBzaW5nbGUgcm93IG9mIHRyZWVzLjxcL3A+XHJcblxyXG48cD5NaXJrb1x1MjAxZnMgbWFjaGluZSB3b3JrcyBhcyBmb2xsb3dzOiBNaXJrbyBzZXRzIGEgaGVpZ2h0IHBhcmFtZXRlciBIIChpbiBtZXRyZXMpLCBhbmQgdGhlIG1hY2hpbmUgcmFpc2VzIGEgZ2lhbnQgc2F3YmxhZGUgdG8gdGhhdCBoZWlnaHQgYW5kIGN1dHMgb2ZmIGFsbCB0cmVlIHBhcnRzIGhpZ2hlciB0aGFuIEggKG9mIGNvdXJzZSwgdHJlZXMgbm90IGhpZ2hlciB0aGFuIEggbWV0ZXJzIHJlbWFpbiBpbnRhY3QpLiBNaXJrbyB0aGVuIHRha2VzIHRoZSBwYXJ0cyB0aGF0IHdlcmUgY3V0IG9mZi4gRm9yIGV4YW1wbGUsIGlmIHRoZSB0cmVlIHJvdyBjb250YWlucyB0cmVlcyB3aXRoIGhlaWdodHMgb2YgMjAsIDE1LCAxMCwgYW5kIDE3IG1ldHJlcywgYW5kIE1pcmtvIHJhaXNlcyBoaXMgc2F3YmxhZGUgdG8gMTUgbWV0cmVzLCB0aGUgcmVtYWluaW5nIHRyZWUgaGVpZ2h0cyBhZnRlciBjdXR0aW5nIHdpbGwgYmUgMTUsIDE1LCAxMCwgYW5kIDE1IG1ldHJlcywgcmVzcGVjdGl2ZWx5LCB3aGlsZSBNaXJrbyB3aWxsIHRha2UgNSBtZXRyZXMgb2ZmIHRoZSBmaXJzdCB0cmVlIGFuZCAyIG1ldHJlcyBvZmYgdGhlIGZvdXJ0aCB0cmVlICg3IG1ldHJlcyBvZiB3b29kIGluIHRvdGFsKS48XC9wPlxyXG5cclxuPHA+TWlya28gaXMgZWNvbG9naWNhbGx5IG1pbmRlZCwgc28gaGUgZG9lc25cdTIwMWZ0IHdhbnQgdG8gY3V0IG9mZiBtb3JlIHdvb2QgdGhhbiBuZWNlc3NhcnkuIFRoYXRcdTIwMWZzIHdoeSBoZSB3YW50cyB0byBzZXQgaGlzIHNhd2JsYWRlIGFzIGhpZ2ggYXMgcG9zc2libGUuIEhlbHAgTWlya28gZmluZCB0aGUgbWF4aW11bSBpbnRlZ2VyIGhlaWdodCBvZiB0aGUgc2F3YmxhZGUgdGhhdCBzdGlsbCBhbGxvd3MgaGltIHRvIGN1dCBvZmYgYXQgbGVhc3QgTSBtZXRyZXMgb2Ygd29vZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMsIE4gKHRoZSBudW1iZXIgb2YgdHJlZXMsIDEgJmxlOyBOICZsZTsgMSAwMDAgMDAwKSBhbmQgTSAoTWlya29cdTIwMWZzIHJlcXVpcmVkIHdvb2QgYW1vdW50LCAxICZsZTsgTSAmbGU7IDIgMDAwIDAwMCAwMDApLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIDEgMDAwIDAwMCAwMDAsIHRoZSBoZWlnaHRzIG9mIGVhY2ggdHJlZSAoaW4gbWV0cmVzKS4gVGhlIHN1bSBvZiBhbGwgaGVpZ2h0cyB3aWxsIGV4Y2VlZCBNLCB0aHVzIE1pcmtvIHdpbGwgYWx3YXlzIGJlIGFibGUgdG8gb2J0YWluIHRoZSByZXF1aXJlZCBhbW91bnQgb2Ygd29vZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBoZWlnaHQgc2V0dGluZy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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