Problem
메뚜기는 서로 같은 거리에 있는 같은 줄에 있는 기둥 위로 점프합니다. 열에는 1 에서 N 까지의 일련 번호가 있습니다. 처음에 Grasshopper는 숫자 1이 있는 기둥에 앉아 있습니다. 현재 막대부터 계산하여 1에서 K 막대로 앞으로 이동할 수 있습니다.
각 열에서 Grasshopper는 몇 개의 금화를 얻거나 잃을 수 있습니다(이 숫자는 각 열에 대해 알려져 있음). 가장 많은 금화를 모으기 위해 Grasshopper가 어떻게 점프해야 하는지 결정합니다. Grasshopper는 뒤로 점프할 수 없습니다.
입력:
- 첫 번째 줄에는 N 및 K(\(2 <= N ,\ K < = 10000\)), 공백으로 구분;
- 두 번째 줄에는 공백으로 구분된 N-2 정수 – Grasshopper가 2번째부터 N-1번째까지 각 열에서 얻는 동전의 수입니다. 이 숫자가 음수이면 Grasshopper는 동전을 잃습니다.
모듈로의 모든 숫자가 10000을 초과하지 않도록 보장합니다.
출력:
- 프로그램은 첫 번째 줄에 Grasshopper가 수집할 수 있는 최대 동전 수를 표시해야 합니다.
- 두 번째 줄은 Grasshopper의 점프 횟수를 표시합니다.
- 세 번째 줄에서 – Grasshopper가 방문한 모든 열의 수(공백으로 오름차순으로 구분).
정답이 여러 개인 경우 그 중 하나를 인쇄하십시오.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
5 3
2 -3 5
|
<사업부>7
<사업부>3
1 2 4 5
|