시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 41472 11693 7331 25.869%

문제

상근이는 나무 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
W3sicHJvYmxlbV9pZCI6IjI4MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0IE1cdWJiZjhcdWQxMzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZmNcdWNjOThcdWM1ZDAgXHViMDk4XHViYjM0XHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU2MCBcdWFjZjNcdWM3NzQgXHViYWE4XHViNDUwIFx1YjlkZFx1ZDU3NFx1YmM4NFx1YjgzOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzgxNVx1YmQ4MFx1YzVkMCBcdWJjOGNcdWJhYTkgXHVkNWM4XHVhYzAwXHViOTdjIFx1YzY5NFx1Y2NhZFx1ZDU4OFx1YjJlNC4gXHVjODE1XHViZDgwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWM5ZDEgXHVhZGZjXHVjYzk4XHVjNzU4IFx1YjA5OFx1YmIzNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWJjOGNcdWJhYTkgXHVkNWM4XHVhYzAwXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1YyBcdWFkNmNcdWM3ODVcdWQ1NWMgXHViYWE5XHVjN2FjXHVjODA4XHViMmU4XHVhZTMwXHViOTdjJm5ic3A7XHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWFkNmNcdWQ1NjBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOVx1YzdhY1x1YzgwOFx1YjJlOFx1YWUzMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjNkOVx1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YjE5Mlx1Yzc3NCBIXHViOTdjIFx1YzljMFx1YzgxNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWM5YzBcdWM4MTVcdWQ1NThcdWJhNzQgXHVkMWIxXHViMGEwXHVjNzc0IFx1YjU0NVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBIXHViYmY4XHVkMTMwIFx1YzcwNFx1Yjg1YyBcdWM2MmNcdWI3N2NcdWFjMDRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVjMThkXHVkNTc0XHVjNzg4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjODA4XHViMmU4XHVkNTc0XHViYzg0XHViOWIwXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjE5Mlx1Yzc3NFx1YWMwMCBIXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWIwOThcdWJiMzRcdWIyOTQgSCBcdWM3MDRcdWM3NTggXHViZDgwXHViZDg0XHVjNzc0IFx1Yzc5OFx1YjliNCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjBhZVx1Yzc0MCBcdWIwOThcdWJiMzRcdWIyOTQgXHVjNzk4XHViOWFjXHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVjMThkXHVkNTc0XHVjNzg4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgMjAsIDE1LCAxMCwgMTdcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViMTkyXHVjNzc0XHViOTdjIDE1XHViODVjIFx1YzljMFx1YzgxNVx1ZDU4OFx1YjJlNFx1YmE3NCwgXHViMDk4XHViYjM0XHViOTdjIFx1Yzc5MFx1Yjk3OCBcdWI0YTRcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDE1LCAxNSwgMTAsIDE1XHVhYzAwIFx1YjQyMCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgNVx1Yzc3OCBcdWIwOThcdWJiMzRcdWM2NDAgMlx1Yzc3OCBcdWIwOThcdWJiMzRcdWI5N2MgXHViNGU0XHVhY2UwIFx1YzlkMVx1YzVkMCBcdWFjMDggXHVhYzgzXHVjNzc0XHViMmU0LiAoXHVjZDFkIDdcdWJiZjhcdWQxMzBcdWI5N2MgXHVjOWQxXHVjNWQwIFx1YjRlNFx1YWNlMCBcdWFjMDRcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ2NThcdWFjYmRcdWM1ZDAgXHViOWU0XHVjNmIwIFx1YWQwMFx1YzJlY1x1Yzc3NCBcdWI5Y2VcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWIwOThcdWJiMzRcdWI5N2MgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjljY1x1ZDA3Y1x1YjljYyBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHVjODM4XHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM4MDFcdWM1YjRcdWIzYzQgTVx1YmJmOFx1ZDEzMFx1Yzc1OCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjOWQxXHVjNWQwIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YzEyNFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjOWQxXHVjNzNjXHViODVjIFx1YWMwMFx1YzgzOFx1YWMwMFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YWUzOFx1Yzc3NCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwLCAxICZsZTsgTSAmbGU7IDIsMDAwLDAwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWM3NTggXHVkNTY5XHVjNzQwIFx1ZDU2ZFx1YzBjMSBNXHVjNzQ0IFx1YjExOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM5ZDFcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWQ1NmRcdWMwYzEgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YjI5NCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWI2MTBcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MDFcdWM1YjRcdWIzYzQgTVx1YmJmOFx1ZDEzMFx1Yzc1OCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjOWQxXHVjNWQwIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YzEyNFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFS08iLCJkZXNjcmlwdGlvbiI6IjxwPkx1bWJlcmphY2sgTWlya28gbmVlZHMgdG8gY2hvcCBkb3duIE0gbWV0cmVzIG9mIHdvb2QuIEl0IGlzIGFuIGVhc3kgam9iIGZvciBoaW0gc2luY2UgaGUgaGFzIGEgbmlmdHkgbmV3IHdvb2RjdXR0aW5nIG1hY2hpbmUgdGhhdCBjYW4gdGFrZSBkb3duIGZvcmVzdHMgbGlrZSB3aWxkZmlyZS4gSG93ZXZlciwgTWlya28gaXMgb25seSBhbGxvd2VkIHRvIGN1dCBhIHNpbmdsZSByb3cgb2YgdHJlZXMuPFwvcD5cclxuXHJcbjxwPk1pcmtvJiMzOTtzIG1hY2hpbmUgd29ya3MgYXMgZm9sbG93czogTWlya28gc2V0cyBhIGhlaWdodCBwYXJhbWV0ZXIgSCAoaW4gbWV0cmVzKSwgYW5kIHRoZSBtYWNoaW5lIHJhaXNlcyBhIGdpYW50IHNhd2JsYWRlIHRvIHRoYXQgaGVpZ2h0IGFuZCBjdXRzIG9mZiBhbGwgdHJlZSBwYXJ0cyBoaWdoZXIgdGhhbiBIIChvZiBjb3Vyc2UsIHRyZWVzIG5vdCBoaWdoZXIgdGhhbiBIIG1ldGVycyByZW1haW4gaW50YWN0KS4gTWlya28gdGhlbiB0YWtlcyB0aGUgcGFydHMgdGhhdCB3ZXJlIGN1dCBvZmYuIEZvciBleGFtcGxlLCBpZiB0aGUgdHJlZSByb3cgY29udGFpbnMgdHJlZXMgd2l0aCBoZWlnaHRzIG9mIDIwLCAxNSwgMTAsIGFuZCAxNyBtZXRyZXMsIGFuZCBNaXJrbyByYWlzZXMgaGlzIHNhd2JsYWRlIHRvIDE1IG1ldHJlcywgdGhlIHJlbWFpbmluZyB0cmVlIGhlaWdodHMgYWZ0ZXIgY3V0dGluZyB3aWxsIGJlIDE1LCAxNSwgMTAsIGFuZCAxNSBtZXRyZXMsIHJlc3BlY3RpdmVseSwgd2hpbGUgTWlya28gd2lsbCB0YWtlIDUgbWV0cmVzIG9mZiB0aGUgZmlyc3QgdHJlZSBhbmQgMiBtZXRyZXMgb2ZmIHRoZSBmb3VydGggdHJlZSAoNyBtZXRyZXMgb2Ygd29vZCBpbiB0b3RhbCkuPFwvcD5cclxuXHJcbjxwPk1pcmtvIGlzIGVjb2xvZ2ljYWxseSBtaW5kZWQsIHNvIGhlIGRvZXNuJiMzOTt0IHdhbnQgdG8gY3V0IG9mZiBtb3JlIHdvb2QgdGhhbiBuZWNlc3NhcnkuIFRoYXQmIzM5O3Mgd2h5IGhlIHdhbnRzIHRvIHNldCBoaXMgc2F3YmxhZGUgYXMgaGlnaCBhcyBwb3NzaWJsZS4gSGVscCBNaXJrbyBmaW5kIHRoZSBtYXhpbXVtIGludGVnZXIgaGVpZ2h0IG9mIHRoZSBzYXdibGFkZSB0aGF0IHN0aWxsIGFsbG93cyBoaW0gdG8gY3V0IG9mZiBhdCBsZWFzdCBNIG1ldHJlcyBvZiB3b29kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycywgTiAodGhlIG51bWJlciBvZiB0cmVlcywgMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDApIGFuZCBNIChNaXJrbyYjMzk7cyByZXF1aXJlZCB3b29kIGFtb3VudCwgMSAmbGU7IE0gJmxlOyAyIDAwMCAwMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiAxIDAwMCAwMDAgMDAwLCB0aGUgaGVpZ2h0cyBvZiBlYWNoIHRyZWUgKGluIG1ldHJlcykuIFRoZSBzdW0gb2YgYWxsIGhlaWdodHMgd2lsbCBleGNlZWQgTSwgdGh1cyBNaXJrbyB3aWxsIGFsd2F5cyBiZSBhYmxlIHRvIG9idGFpbiB0aGUgcmVxdWlyZWQgYW1vdW50IG9mIHdvb2QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgaGVpZ2h0IHNldHRpbmcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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