Problem
Belalang melompat pada lajur yang terletak pada garisan yang sama pada jarak yang sama antara satu sama lain. Lajur mempunyai nombor siri daripada 1 hingga N . Pada mulanya, Grasshopper duduk pada jawatan dengan nombor 1. Ia boleh melompat ke hadapan daripada bar 1 kepada K, mengira daripada bar semasa.
Pada setiap lajur, Grasshopper boleh mendapat atau kehilangan beberapa syiling emas (nombor ini diketahui untuk setiap lajur). Tentukan bagaimana Belalang perlu melompat untuk mengumpul syiling emas terbanyak. Perlu diingat bahawa Belalang tidak boleh melompat ke belakang.
Input:
- baris pertama mengandungi dua nombor asli: N dan K (\(2 <= N ,\ K < = 10000\)), diasingkan ruang;
- dalam baris kedua, integer N-2 yang dipisahkan ruang – bilangan syiling yang Grasshopper dapat pada setiap lajur, dari ke-2 hingga N-1th. Jika nombor ini negatif, Belalang kehilangan syiling.
Ia dijamin bahawa semua nombor dalam modulo tidak melebihi 10000.
Output:
- dalam baris pertama, program harus memaparkan bilangan maksimum syiling yang dapat dikumpulkan oleh Belalang;
- baris kedua memaparkan bilangan lompatan Grasshopper;
- pada baris ketiga – bilangan semua lajur yang dilawati oleh Grasshopper (dipisahkan dengan ruang dalam tertib menaik).
Jika terdapat beberapa jawapan yang betul, cetak mana-mana daripadanya.
Contoh
| # |
Input |
Output |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|