叶子合并leaves

在一个美丽的秋天，丽丽每天经过的笔直花园小巷中落满了树叶。小巷中共有 $N$ 片树叶，它们排列在一条直线上，每片树叶都有一个重量值，相邻两片树叶之间的距离均为 $1$ 。所有树叶按照从左到右的顺序编号为 $1$ 到 $N$ 。

丽丽决定将这些树叶合并成 $K$ 堆，并分 $K$ 天完成，每天整理一堆。移动一片树叶所消耗的能量等于该树叶的重量与移动距离的乘积。由于丽丽每天都从右向左经过小巷，因此树叶只能向左移动。

请计算丽丽将所有树叶合并成 $K$ 堆所需消耗的最少能量。

输入格式

第一行包含两个用空格分隔的正整数 $N$ 和 $K$ 。

接下来 $N$ 行，每行包含一个正整数。其中第 $i+1$ 行的整数表示第 $i$ 片树叶的重量 $w_i$ 。

输出一个整数，表示将所有树叶合并成 $K$ 堆所需消耗的最少能量。

本题题面与测试数据整理自 BZOJ。