Yeni Əmber Labirinti
Amber şahzadəsi Korvin, təcili olaraq bildiyi ən uzaq kölgəyə getməli oldu. Amber şahzadələri üçün ən sürətli səyahət yolu Amber Labirintidir. Lakin Korvinin çox vacib işləri olduğundan, yeraltına enib Amber Labirintindən istifadə etmək istəmədi. Bunun əvəzinə, Dvorkinin çəkdiyi Yeni Labirintdən istifadə etməyə qərar verdi. Lakin bu Labirint göründüyü qədər sadə deyil...
Yeni Labirint ardıcıl hücrələrdən ibarətdir və bu hücrələr 1-dən N-ə qədər nömrələnib. i nömrəli hücrədən i+2 (əgər i+2 ≤ N) və i+3 (əgər i+3 ≤ N) nömrəli hücrələrə keçmək mümkündür. Hər bir hücrədə müəyyən miqdarda qızıl sikkə k_i var. Labirinti keçmək üçün, sıfırıncı hücrədən başlayaraq yuxarıda təsvir olunan qaydalara uyğun irəliləmək və bu zaman keçdiyiniz hücrələrdəki bütün sikkələri toplamaq lazımdır. Səyahətin son məqsədi N nömrəli hücrəyə çatmaqdır. Yalnız N nömrəli hücrəyə çatdıqdan sonra (Kainatın istənilən yerinə) daha da səyahət etmək mümkündür, əgər siz maksimum miqdarda sikkə toplasanız. Korvinə Yeni Amber Labirintini keçərkən maksimum neçə sikkə toplaya biləcəyini öyrənməyə kömək edəcək bir proqram yazın.
Giriş verilənləri
Giriş faylının birinci sətirində təbii ədəd N (2 ≤ N ≤ 100000), ikinci sətirdə isə bir boşluqla ayrılmış N tam ədəd, k_i – i nömrəli hücrədə olan sikkələrin sayı (0 ≤ k_i ≤ 1000).
Çıxış verilənləri
Çıxış faylında bir tam ədəd yazın – labirinti keçərkən toplaya biləcəyiniz maksimum sikkə sayı.