Ծածկույթ

Տրված է չափի վանդակավոր դաշտ։ Յուրաքանչյուր վանդակում գրված է մեկ ամբողջ թիվ։ Ծածկույթ է կոչվում վանդակներից ընտրված որևէ բազմություն, որը ծածկվում է (կարելի է նաև ընտրել 0 հատ վանդակ)։ Ծածկույթը կոչվում է գեղեցիկ, եթե գոյություն չունեն երկու ծածկված հարևան վանդակներ։ Հարևան կոչվում են ընդհանուր կողմ ունեցող վանդակները։

Ծածկույթի արժեքը դա ծածկված վանդակներում գրված թվերի գումարն է։ Պահանջվում է գտնել գեղեցիկ ծածկույթների մեջ ամենամեծ արժեքը ունեցող ծածկույթի արժեքը։

Մուտքային տվյալներ

Առաջին տողում տրված են և թվերը, որոնք ցույց են տալիս վանդակավոր դաշտի չափը։

Հաջորդ տողերից -րդում տրված է թիվ՝ , վանդակավոր դաշտի -րդ տողի վրա գրված թվերը։

Ելքային տվյալներ

Հարկավոր է արտածել գեղեցիկ ծածկույթների մեջ ամենամեծ արժեքը ունեցող ծածկույթի արժեքը։

Օրինակներ

1 5
1 2 -1 2 1

4

2 5
2 3 4 5 6
6 5 4 3 2

20

3 4
1 5 1 5
5 1 5 16
1 5 1 5

31

Ենթախնդիրներ