Qaçış#10152
Bessi inək daha güclü idmançı olmaq istəyir, buna görə də düz dəqiqə qaçış zolağında qaçmağa qərar verib. Hər dəqiqə ərzində o, ya qaça bilər, ya da bütün dəqiqəni istirahət edərək keçirə bilər.
Bessinin qaça biləcəyi ümumi məsafə onun yorğunluq əmsalından asılıdır, bu əmsal əvvəlcə -a bərabərdir. Əgər Bessi -ci dəqiqədə qaçırsa, o, d_i məsafəsini qaçır və onun yorğunluq əmsalı artır. Yorğunluq əmsalı heç vaxt -dən böyük ola bilməz.
Əgər Bessi istirahət edirsə, onun yorğunluq əmsalı azalır, lakin mənfi ola bilməz. Bessi yalnız yorğunluq əmsalı -a çatdıqda yenidən qaçmağa başlaya bilər. Bu anda o seçim edə bilər: ya qaçmağa davam edir, ya da istirahətini davam etdirir.
dəqiqəlik məşqin sonunda Bessinin yorğunluq əmsalı düz olmalıdır; əks halda günün qalan hissəsi üçün kifayət qədər enerjisi qalmayacaq.
Bütün bu qaydalara riayət edərək Bessinin qaça biləcəyi maksimum ümumi məsafəni tapın.
Birinci sətirdə iki tam ədəd verilir: n~(1 \le n \le 10^4) və m~(1 \le m \le 500).
Sonrakı sətir d_1, d_2, \ldots, d_n~(1 \le d_i \le 1000) tam ədədlərini ehtiva edir, burada d_i — Bessinin -ci dəqiqədə qaçmaq qərarına gəldiyi halda qaçacağı məsafədir.
Bütün verilmiş qaydalara riayət edərək Bessinin qaça biləcəyi maksimum ümumi məsafəni bildirən bir tam ədəd çıxarın.
Nümunə 1