Զանգվածը բաժանել, որպեսզի առավելագույն գումարը լինի հնարավորինս փոքր
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով
n ամբողջ թվեր և մեկ ամբողջ թիվ k, պետք է բաժանի զանգվածը k հաջորդական մասերի այնպես, որ առաջացած ենթազանգվածների առավելագույն գումարը լինի որքան հնարավոր է փոքր:Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n (1 ≤ n ≤ ) և k (1 ≤ k ≤ n):Հաջորդ տողում տրված են բացատներով բաժանված ( ≤ ≤ ):
Ելք
Ծրագիրը պետք է տպի ենթազանգվածների առավելագույն գումարի ամենափոքր հնարավոր արժեքը:
Օրինակներ
Մուտք | Ելք |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Բացատրություն
[1 2 3] [6 2]⇒ ենթազանգվածի առավելագույն գումարը 6 + 2 = 8
[1 2] [10] [3 2]⇒ ենթազանգվածի առավելագույն գումարը 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB