Problem
Châu chấu nhảy trên các cột nằm trên cùng một đường thẳng với khoảng cách bằng nhau. Các cột có số thứ tự từ 1 đến N . Lúc đầu, Châu chấu ngồi trên cột có số 1. Nó có thể chuyển tiếp từ 1 sang K thanh, tính từ thanh hiện tại.
Trên mỗi cột, Grasshopper có thể kiếm được hoặc mất một vài đồng tiền vàng (con số này được biết cho mỗi cột). Xác định cách Grasshopper cần nhảy để thu thập được nhiều tiền vàng nhất. Hãy nhớ rằng Châu chấu không thể nhảy lùi.
Đầu vào:
- dòng đầu tiên chứa hai số tự nhiên: N và K (\(2 <= N ,\ K < = 10000\)), phân tách bằng dấu cách;
- ở dòng thứ hai, các số nguyên N-2 phân tách bằng dấu cách – số xu Grasshopper nhận được trên mỗi cột, từ thứ 2 đến N-1th. Nếu số này là số âm, Châu chấu sẽ mất xu.
Đảm bảo rằng tất cả các số theo modulo không vượt quá 10000.
Đầu ra:
- trong dòng đầu tiên, chương trình sẽ hiển thị số xu tối đa mà Châu chấu có thể thu thập;
- dòng thứ hai hiển thị số lần châu chấu nhảy;
- trên dòng thứ ba – số của tất cả các cột mà Grasshopper đã truy cập (được phân tách bằng dấu cách theo thứ tự tăng dần).
Nếu có nhiều câu trả lời đúng, hãy in bất kỳ câu nào trong số đó.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|