Տների կողոպուտ
Դուք պլանավորում եք կողոպտել մի փողոցի վրա գտնվող տները։ Այնտեղ կան
n տներ, և նախապես հայտնի է, թե յուրաքանչյուր տնից որքան գումար կարող եք գողանալ։ Սակայն անվտանգության համակարգը ոստիկանությանը տեղեկացնում է, եթե նույն գիշերվա ընթացքում կողոպտվում են իրար հարևան երկու տներ։Հարցն այն է, թե մեկ գիշերվա ընթացքում ի՞նչ առավելագույն գումար կարող եք ստանալ՝ առանց բռնվելու:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ )։Հաջորդ տողում տրված են
n բացատներով բաժանված ամբողջ թվեր (1 ≤ ≤ ), որոնք ցույց են տալիս, թե որքան գումար կարելի է գողանալ յուրաքանչյուր տնից։Ելք
Ծրագիրը պետք է առավելագույն գումարը, որը հնարավոր է ստանալ առանց բռնվելու։
Օրինակներ
Մուտք | Ելք |
4
1 2 5 1 | 6 |
5
3 17 12 3 7 | 24 |
Բացատրություն
- 1 + 5
- 17 + 7 (միջակայքում գտնվող տները բաց թողնելով)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB