题目描述
汶川大地震发生已经有两年了。地震灾区的重建工作有许多工作要做，其中学校的重建被放在了重要的议事日程上：
在一条新建的公路两旁，有n个村庄，编号为1,2,…,n。（3≤n≤100），每个村庄有一定数量的小学生，村庄之间的距离也已知。例如n=3时，下图给出了三个村庄的相关情况：
村庄1的学生数24,村庄2的学生数18,村庄3的学生数31。
村庄1和村庄2之间距离为10, 村庄2和村庄3之间的距离为8。
10 8
①————②————③
24 18 31
现在要在村庄中建k个学校（1≤k≤45）,比如上图中k=2时，建二个学校，此时有三种方案：
村庄1 村庄2 村庄3学生走到村庄2, 学生走的距离和为31*8=248
村庄1 村庄3 村庄2学生走到村庄3（就近入学），学生走的距离和为18*8＝144
村庄2 村庄3 此时村庄1的学生走到村庄2的距离和为24*10=240
显然，方案２最好。
当给出村庄数n，每个村庄的学生数、村庄之间的距离以及要建的学校数k之后，求出
合理的建学校的方案，使学生走的距离和为最少。
输入
第一行2个整数，表示村庄数n，学校数k 第二行n个整数，表示每个村庄学生数（0＜每个村庄学生数≤100 ) 第三行n-1个数，分别表示村庄i到村庄i+1之间距离（1≤距离≤100，1≤i≤n-1）
输出
一个整数，即学生走的距离和的最小值
样例输入输出
输入#1
复制
3 2
24 18 31
10 8
提示