참호전
시간 제한1초메모리 제한1024 MB
N개의 참호에 M명을 배치해 각 참호를 이기려면 적군보다 한 명 많아야 하고, 연속한 한 구간은 적군 합이 K 이하일 때만 폭파할 수 있을 때 이길 수 있는 참호 수의 최댓값을 구한다.
문제
적군의 참호 개가 일렬로 늘어서 있다. 국군의 지휘관은 각 참호에 대응하기 위해 적군의 참호를 늘어선 순서대로 번의 번호를 붙였고, 번 참호에는 적군이 명 배치되어 있다는 사실을 알아냈다.
지휘관은 참호전을 위해 각 적군 참호에 대응하는 아군 참호를 맞은편에 개씩 모두 설치했고, 휘하에 있는 명의 국군을 각각의 아군 참호에 나누어 배치하려 한다. 각 아군 참호에는 명 이상의 국군을 배치할 수 있고, 아군 참호별로 맞은편의 적군 참호에게서 승리하기 위해서는 맞은편의 적군 참호에 있는 적군 수보다 많은 국군을 아군 참호에 배치해야 한다.
지휘관은 폭격기로 폭탄을 하나 투하해 특정한 범위 내 연속한 번호의 적군 참호를 모두 폭파할 수 있다. 이때 지휘관은 폭격기의 폭탄 투하 위치와 폭탄의 폭파 범위를 설정할 수 있으며, 적군 참호를 폭파하면 해당 적군 참호에게서 승리한 것으로 간주한다. 하지만 동맹국에서 폭탄에 의한 인명피해를 최소화해달라는 요청이 있었다. 따라서 폭격기로 폭탄을 투하하지 않거나, 투하한다면 폭파한 적군 참호에 배치된 적군 수의 합이 명 이하여야 한다.
지휘관은 폭격기의 폭탄 투하 위치와 폭탄의 폭파 범위를 설정하고 각 아군 참호에 배치할 국군의 수를 적절히 나누어 최대한 많은 적군 참호에게서 승리하도록 전략을 세우려 한다. 지휘관이 승리할 수 있는 적군 참호의 최대 개수를 구하여라.
입력
첫 번째 줄에 적군 참호의 수 , 국군의 수 , 폭탄의 인명피해 제한 가 공백으로 구분되어 정수로 주어진다.
두 번째 줄에 각 적군 참호에 배치된 적군의 수 이 공백으로 구분되어 정수로 주어진다.
출력
첫 번째 줄에 지휘관이 승리할 수 있는 적군 참호의 최대 개수를 출력한다.