울퉁불퉁한 땅 위에 시멘트를 부어 최대한 높이 차가 적도록 만들고자 한다.
시멘트의 총량과 채울 수 있는 시멘트의 높이 중 가장 큰 값을 출력하세요.
제한 사항
- 영역은 2차원으로 이루어져 있으며 총 면적의 높이는 h, 너비는 w로 주어진다.
- 기둥의 높이는 왼쪽부터 차례대로 w개 만큼 주어진다.
- 이때, 기둥의 높이는 0 이상 h 이하이다.
- 기둥은 단단하기 때문에 기둥 내부의 틈이 있거나 물이 샐 수 없는 구조이다.
- 기둥과 기둥 사이에만 시멘트를 채울 수 있다.
입출력 예
input h = 7 w = 6 column = [5, 4, 3, 7, 2, 4] output 5 2 input h = 7 w = 6 column = [7, 2, 5, 4, 1, 6] output 12 5
힌트
