题目描述

在一条大路一旁有许多栋楼，每栋楼里有许多小学生（哈哈哈一波小学生来袭！）。但是这条路上没有小学！！！！所以唯恐世界不乱的牛 A 打算在路上（汽车什么的都不敢来这个小学生云集的地方咯，所以不用担心安全问题）任选几点（可以和楼重合，当然也可以不重合）建立小学，且使所有小学生上学走的路程之和最短。牛 A 发现修建一所小学根本无法满足他唯恐世界不乱的（变态）心理，所以他准备建立 $k$ 所小学。

输入格式

第一行 $2$ 个整数，表示楼数 $n$，学校数 $k$（$1 \le n, k \le 100$）。

第二行 $n$ 个整数，表示每栋楼的学生数 $a_i$（$0 < a_i \le 100$）。

第三行 $n-1$ 个数，分别表示楼 $i$ 到楼 $i+1$ 之间的距离 $d_i$（$1 \le d_i \le 100, 1 \le i \le n-1$）。

输出格式

输出学生走的距离和的最小值。

3 2
24 18 31
10 8

144