벌목공 미코는 N 미터의 나무를 잘라야 한다. 이 것은 쉬운 작업이다. 왜냐 하면 그는 아주 쌈박한 나무 자르는 기계를 가지고 있다. 그러나 미코는 나무의 한 지점 만을 자르는 것이 허용된다.
미코의 기계는 다음과 같이 작동 된다: 미코가 파라미터 H(미터)로 기계를 세팅한다. 그러면 기계는 해당 높이로 큰 톱날이 울려 지고 H 보다 큰 모든 나무를 자른다. (물론 그 보다 낮은 나무는 건드려지지 않는다).
예를 들어 , 잘려 질 나무가 높이가 20, 15, 10, and 17 metres 라면 미코는 15 미터로 톱날을 올려서 자른다면 잘려는 나무의 높이는 15, 15, 10, and 15 metres가 된다. 그러면 첫 번째 나무에서 5 미터를 4 번째 나무에서 2 미터를 얻어서 총 7 미터의 나무를 얻을 수 있다.
미코는 생태학적으로 구두쇠라 가능하다면 더 많은 나무가 잘리는 것을 원하지 않는다. 이것이 그가 가능한 톱날을 높이 두기를 원하는 이유이다.
적어도 M 미터의 나무를 얻는 데 그가 할 수 있는 최대 톱날의 높이를 구하라.
Mirko's machine works as follows: Mirko sets a height parameter H (in metres), and the machine raises a giant sawblade to that height and cuts off all tree parts higher than H (of course, trees not higher than H meters remain intact). Mirko then takes the parts that were cut off. For example, if the tree row contains trees with heights of 20, 15, 10, and 17 metres, and Mirko raises his sawblade to 15 metres, the remaining tree heights after cutting will be 15, 15, 10, and 15 metres, respectively, while Mirko will take 5 metres off the first tree and 2 metres off the fourth tree (7 metres of wood in total).
Mirko is ecologically minded, so he doesn't want to cut off more wood than necessary. That's why he wants to set his sawblade as high as possible. Help Mirko find the maximum integer height of the sawblade that still allows him to cut off at least M metres of wood.
입력 4 7 20 15 10 17 출력 15 입력 5 20 4 42 40 26 46 출력 36
출처:coci 2011-2012 contest5 2/6