시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB194468572933555326.130%

문제

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

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

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 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

예제 입력 2

5 20
4 42 40 26 46

예제 출력 2

36
W3sicHJvYmxlbV9pZCI6IjI4MDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjNzkwXHViOTc0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMDk4XHViYjM0IE1cdWJiZjhcdWQxMzBcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHViMmU0LiBcdWFkZmNcdWNjOThcdWM1ZDAgXHViMDk4XHViYjM0XHViOTdjIFx1YWQ2Y1x1Yzc4NVx1ZDU2MCBcdWFjZjNcdWM3NzQgXHViYWE4XHViNDUwIFx1YjlkZFx1ZDU3NFx1YmM4NFx1YjgzOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzgxNVx1YmQ4MFx1YzVkMCBcdWJjOGNcdWJhYTkgXHVkNWM4XHVhYzAwXHViOTdjIFx1YzY5NFx1Y2NhZFx1ZDU4OFx1YjJlNC4gXHVjODE1XHViZDgwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWM5ZDEgXHVhZGZjXHVjYzk4XHVjNzU4IFx1YjA5OFx1YmIzNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWJjOGNcdWJhYTkgXHVkNWM4XHVhYzAwXHViOTdjIFx1YjBiNFx1YzhmY1x1YzVjOFx1YWNlMCwgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1YyBcdWFkNmNcdWM3ODVcdWQ1NWMgXHViYWE5XHVjN2FjXHVjODA4XHViMmU4XHVhZTMwXHViOTdjJm5ic3A7XHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWFkNmNcdWQ1NjBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOVx1YzdhY1x1YzgwOFx1YjJlOFx1YWUzMFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjNkOVx1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YjE5Mlx1Yzc3NCBIXHViOTdjIFx1YzljMFx1YzgxNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWM5YzBcdWM4MTVcdWQ1NThcdWJhNzQgXHVkMWIxXHViMGEwXHVjNzc0IFx1YjU0NVx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBIXHViYmY4XHVkMTMwIFx1YzcwNFx1Yjg1YyBcdWM2MmNcdWI3N2NcdWFjMDRcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVjMThkXHVkNTc0XHVjNzg4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjODA4XHViMmU4XHVkNTc0XHViYzg0XHViOWIwXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YjE5Mlx1Yzc3NFx1YWMwMCBIXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWIwOThcdWJiMzRcdWIyOTQgSCBcdWM3MDRcdWM3NTggXHViZDgwXHViZDg0XHVjNzc0IFx1Yzc5OFx1YjliNCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjBhZVx1Yzc0MCBcdWIwOThcdWJiMzRcdWIyOTQgXHVjNzk4XHViOWFjXHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVjMThkXHVkNTc0XHVjNzg4XHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgMjAsIDE1LCAxMCwgMTdcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHViMTkyXHVjNzc0XHViOTdjIDE1XHViODVjIFx1YzljMFx1YzgxNVx1ZDU4OFx1YjJlNFx1YmE3NCwgXHViMDk4XHViYjM0XHViOTdjIFx1Yzc5MFx1Yjk3OCBcdWI0YTRcdWM3NTggXHViMTkyXHVjNzc0XHViMjk0IDE1LCAxNSwgMTAsIDE1XHVhYzAwIFx1YjQyMCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgNVx1Yzc3OCBcdWIwOThcdWJiMzRcdWM2NDAgMlx1Yzc3OCBcdWIwOThcdWJiMzRcdWI5N2MgXHViNGU0XHVhY2UwIFx1YzlkMVx1YzVkMCBcdWFjMDggXHVhYzgzXHVjNzc0XHViMmU0LiAoXHVjZDFkIDdcdWJiZjhcdWQxMzBcdWI5N2MgXHVjOWQxXHVjNWQwIFx1YjRlNFx1YWNlMCBcdWFjMDRcdWIyZTQpIFx1YzgwOFx1YjJlOFx1YWUzMFx1YzVkMCBcdWMxMjRcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWI2MTBcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDY1OFx1YWNiZFx1YzVkMCBcdWI5ZTRcdWM2YjAgXHVhZDAwXHVjMmVjXHVjNzc0IFx1YjljZVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViOWNjXHVkMDdjXHViOWNjIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWFjMDBcdWM4MzhcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzgwMVx1YzViNFx1YjNjNCBNXHViYmY4XHVkMTMwXHVjNzU4IFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWM5ZDFcdWM1ZDAgXHVhYzAwXHVjODM4XHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM4MDhcdWIyZThcdWFlMzBcdWM1ZDAgXHVjMTI0XHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMTkyXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMDk4XHViYjM0XHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHVjODM4XHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVhZTM4XHVjNzc0IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxLDAwMCwwMDAsIDEgJmxlOyBNICZsZTsgMiwwMDAsMDAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMDk4XHViYjM0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NDAgXHVkNTZkXHVjMGMxIE1cdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM5ZDFcdWM1ZDAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWQ1NmRcdWMwYzEgXHVhYzAwXHVjODM4XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YjI5NCAxLDAwMCwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWI2MTBcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MDFcdWM1YjRcdWIzYzQgTVx1YmJmOFx1ZDEzMFx1Yzc1OCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjOWQxXHVjNWQwIFx1YWMwMFx1YzgzOFx1YWMwMFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjODA4XHViMmU4XHVhZTMwXHVjNWQwIFx1YzEyNFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFS08iLCJkZXNjcmlwdGlvbiI6IjxwPkx1bWJlcmphY2sgTWlya28gbmVlZHMgdG8gY2hvcCBkb3duIE0gbWV0cmVzIG9mIHdvb2QuIEl0IGlzIGFuIGVhc3kgam9iIGZvciBoaW0gc2luY2UgaGUgaGFzIGEgbmlmdHkgbmV3IHdvb2RjdXR0aW5nIG1hY2hpbmUgdGhhdCBjYW4gdGFrZSBkb3duIGZvcmVzdHMgbGlrZSB3aWxkZmlyZS4gSG93ZXZlciwgTWlya28gaXMgb25seSBhbGxvd2VkIHRvIGN1dCBhIHNpbmdsZSByb3cgb2YgdHJlZXMuPFwvcD5cclxuXHJcbjxwPk1pcmtvJiMzOTtzIG1hY2hpbmUgd29ya3MgYXMgZm9sbG93czogTWlya28gc2V0cyBhIGhlaWdodCBwYXJhbWV0ZXIgSCAoaW4gbWV0cmVzKSwgYW5kIHRoZSBtYWNoaW5lIHJhaXNlcyBhIGdpYW50IHNhd2JsYWRlIHRvIHRoYXQgaGVpZ2h0IGFuZCBjdXRzIG9mZiBhbGwgdHJlZSBwYXJ0cyBoaWdoZXIgdGhhbiBIIChvZiBjb3Vyc2UsIHRyZWVzIG5vdCBoaWdoZXIgdGhhbiBIIG1ldGVycyByZW1haW4gaW50YWN0KS4gTWlya28gdGhlbiB0YWtlcyB0aGUgcGFydHMgdGhhdCB3ZXJlIGN1dCBvZmYuIEZvciBleGFtcGxlLCBpZiB0aGUgdHJlZSByb3cgY29udGFpbnMgdHJlZXMgd2l0aCBoZWlnaHRzIG9mIDIwLCAxNSwgMTAsIGFuZCAxNyBtZXRyZXMsIGFuZCBNaXJrbyByYWlzZXMgaGlzIHNhd2JsYWRlIHRvIDE1IG1ldHJlcywgdGhlIHJlbWFpbmluZyB0cmVlIGhlaWdodHMgYWZ0ZXIgY3V0dGluZyB3aWxsIGJlIDE1LCAxNSwgMTAsIGFuZCAxNSBtZXRyZXMsIHJlc3BlY3RpdmVseSwgd2hpbGUgTWlya28gd2lsbCB0YWtlIDUgbWV0cmVzIG9mZiB0aGUgZmlyc3QgdHJlZSBhbmQgMiBtZXRyZXMgb2ZmIHRoZSBmb3VydGggdHJlZSAoNyBtZXRyZXMgb2Ygd29vZCBpbiB0b3RhbCkuPFwvcD5cclxuXHJcbjxwPk1pcmtvIGlzIGVjb2xvZ2ljYWxseSBtaW5kZWQsIHNvIGhlIGRvZXNuJiMzOTt0IHdhbnQgdG8gY3V0IG9mZiBtb3JlIHdvb2QgdGhhbiBuZWNlc3NhcnkuIFRoYXQmIzM5O3Mgd2h5IGhlIHdhbnRzIHRvIHNldCBoaXMgc2F3YmxhZGUgYXMgaGlnaCBhcyBwb3NzaWJsZS4gSGVscCBNaXJrbyBmaW5kIHRoZSBtYXhpbXVtIGludGVnZXIgaGVpZ2h0IG9mIHRoZSBzYXdibGFkZSB0aGF0IHN0aWxsIGFsbG93cyBoaW0gdG8gY3V0IG9mZiBhdCBsZWFzdCBNIG1ldHJlcyBvZiB3b29kLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHNwYWNlLXNlcGFyYXRlZCBwb3NpdGl2ZSBpbnRlZ2VycywgTiAodGhlIG51bWJlciBvZiB0cmVlcywgMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDApIGFuZCBNIChNaXJrbyYjMzk7cyByZXF1aXJlZCB3b29kIGFtb3VudCwgMSAmbGU7IE0gJmxlOyAyIDAwMCAwMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiAxIDAwMCAwMDAgMDAwLCB0aGUgaGVpZ2h0cyBvZiBlYWNoIHRyZWUgKGluIG1ldHJlcykuIFRoZSBzdW0gb2YgYWxsIGhlaWdodHMgaXMgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvJm5ic3A7TSwgdGh1cyBNaXJrbyB3aWxsIGFsd2F5cyBiZSBhYmxlIHRvIG9idGFpbiB0aGUgcmVxdWlyZWQgYW1vdW50IG9mIHdvb2QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgaGVpZ2h0IHNldHRpbmcuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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