题目描述

某星球发生灾难，他们需要乘坐飞船逃离该星球。该星球有$N$个居民，已经排好队，要求按照队伍的顺序登船。飞船只能飞行$M$趟，为了控制成本，需要将飞船的承重设计的尽可能的小，给定$N$个居民的体重，求飞船的承重。

输入格式

第一行，两个整数$N$和$M$，意义如题所述。 第二行，$N$个整数，表示居民的体重。

输出格式

一个整数，意义如题所述。

样例

8 3
40 30 50 80 100 120 40 60

220

数据范围

• 对于 $100\%$ 的测试数据满足：$1≤n≤1000000$，$1≤m≤100000$。