Description

山谷中住着一个巨大的蚂蚁王国，蚁穴外有一个整洁的广场，天气晴好时蚁群常在那里举行各种活动。这天夜里，天降果子尘，第2天，广场上堆满了大大小小的果子堆，蚁哨出去数了数共有n堆，蚁后要求她的臣民将广场上的果子堆清理掉。具体办法是：每次可以把广场上的任意k堆果子合并成一堆，重复进行直至所有的果子堆最终合并成一堆。规定（1）：2≤k≤m≤n，m由蚁后指定，（2）：每次合并k堆果子的代价是这k堆果子子的重量和。
你的任务是，对给定的n和m，计算出将n堆果子最终合并成1堆的最小总代价。
例如，广场上有7堆果子，其重量分别为45，13，12，16，9，5，22。当m=3时，这些果子堆合并成一堆的最小总代价为199。当m=5时，这些果子堆合并成一堆的最小总代价为148。

Input

包含n+2个整数（n≤100000），其中第一行2个正整数，分别表示n堆果子和每次合并时可以合并的最大堆数m，从第二行开始有n个数，表示n堆果子的重量（1～500），数与数之间用空格隔开。

Output

只包含一个正整数，表示将n堆果子合并成1堆所需的最小总代价。

Sample 1

Input

7 3
45 13 12 16 9 5 22

Output

199

Limitation

1s, 128Mb for each test case.

Hint

Free Pascal Code

var a,b:longint;
begin
    readln(a,b);
    writeln(a+b);
end.

C Code

#include <stdio.h>
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++ Code

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

Python Code

a, b = [int(i) for i in raw_input().split()]
print(a + b)

Java Code

import java.io.*;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

Source

Vijos Original