Տուրիզմ
Ինչպես հիշում եք, Հայկը դեռ մարզային փուլին գնում էր դպրոց, իսկ հիմա արդեն միայնակ պետք է գնա ճանապարհորդության։ Հայկը պլանավորում է այցելել իրարից տարբեր
n տեսարժան վայրեր։Տեսարժան վայրերը համարակալված են 1ից n թվերով, և Հայկը պետք է այցելի դրանք ճիշտ նույն հերթականությամբ։ Մեկ օրում Հայկը կարող է այցելել ամենաշատը k տեսարժան վայրեր և ցանկանում է պլանավորել իր ճանապարհորդությունն այնպես, որ ծախսած օրերի քանակը լինի հնարավորինս քիչ։Տեսարժան վայրերից յուրաքանչյուրը ունի գեղեցկության չափանիշ, որոնք ձեզ տրված են։ Հայկը ամեն օր ստանում է իր այցելած տեսարժան վայրերի գեղեցկության չափանիշներից առավելագույնին համարժեք հաճույք։ Ձեր խնդիրն է պլանավորել Հայկի ճանապարհորդությունն այնպես, որ նա այդ ճանապարհորդությունից ստանա հնարավորինս շատ հաճույք, այսինքն բոլոր օրերում ստացած հաճույքների գումարը լինի հնարավորինս մեծ։Մուտքային տվյալներ
Առաջին տողում տրված է երկու բնական թիվ՝
n և k (1 ≤ k ≤ n ≤ 300 թեստերի առաջին խմբի համար և 1 ≤ k ≤ n ≤n տողերից յուրաքանչյուրում տրված է մեկ բնական թիվ՝ a[i] (1 ≤ a[i] ≤iրդ վայրի գեղեցկության չափանիշը:Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ առավելագույն հաճույքը, որը Հայկը կարող է ստանալ։
Օրինակ
Մուտք. | Ելք. |
5 3
2 5 7 1 4 | 12 |
Բացատրություն
Հայկը ցանկանում է այցելել բոլոր տեսարժան վայրերը հնարավորինս քիչ օրերում, և նա այս օրինակում կարող է դա անել
2 օրում․- Առաջին օր. Հայկը կայցելի առաջին երկու տեսարժան վայրերը՝ ստանալով
max(a[1], a[2]) = 5հաճույք,
- Երկրորդ օր. Հայկը կայցելի մնացած երեք տեսարժան վայրերը՝ ստանալով
max(a[3], a[4], a[5]) = 7հաճույք:
Աղբյուրը՝ Հանրապետական 2021
Constraints
Time limit: 5 seconds
Memory limit: 1000 MB
Output limit: 1 MB