문제
컴퓨터공학과에 재학중인 한재는 같은 대학교의 철학과에 재학중인 연수랑 사귀는 사이다.
연수와 한재는 수업이 끝나면 시공의 폭풍이 부는 계단에서 계단 오르기 게임을 한다. 계단 오르기 게임이란 각 계단에 점수를 부여하고 연수와 한재가 손 잡고 계단을 올라가면서 각 계단의 점수를 획득하는 게임이다.
비록 알파고를 만들 수는 없지만, 한재는 이 게임의 알파고를 만들어서 연수에게 보여주고 싶어한다. 한재를 도와 계단오르기 알파고를 만들어 보자.
1. 시작은 가장 아래 계단에서 시작한다. 2. 시공의 폭풍이 부는 계단은 매우 높아서 연수 한재 커플이 한 번에 건너뛸 수 있는 계단은 K개로 제한된다. 중복해서 계단을 밟을 수는 없다. 3. 계단을 다 밟을 수는 없고 최대 P개의 계단만 밟을 수 있다고 한다. 4. 다음 시간 수업이 있어서 밟을 수 있는 계단의 개수를 다 밟고 나서 계단 끝 (예제에서는 ‘5’라고 적혀있는 칸의 다음 칸) 에 도착해야 한다.
입력
첫 번째 줄에는 시공의 폭풍이 부는 계단의 개수 N(5≤N≤1,000)과, 총 밟을 수 있는 계단의 개수 P(5≤P≤1,000)와,, 연수와 한재가 한 번에 넘을 수 있는 계단의 개수 K(1≤K≤10)가 주어진다.
두 번째 줄부터 N+1번째 줄 까지는 각 계단에 매겨진 점수가 주어진다. 각 계단에 매겨진 점수는 1,000을 넘지 않는다.
출력
연수와 한재가 획득할 수 있는 최대 점수와 밟은 계단의 점수를 출력하여라. 정해진 룰대로 계단을 밟을 수 없는 경우는 존재하지 않는다.
예제
7 5 2
24
32
10
7
12
13
5
91
24 32 10 12 13
출처
bighilljae
로그인해야 코드를 작성할 수 있어요.