学校选址 II

题目描述

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

输入输出格式

输入格式


第一行2个整数,表示楼数n,学校数k(1<=n,k<=100) 第二行n个整数,表示每栋楼的学生数(0<每栋楼学生数≤100 ) 第三行n-1个数,分别表示楼i到楼i+1之间距离(1≤距离≤100,1≤i≤n-1)

输出格式


即学生走的距离和的最小值

输入输出样例

输入样例 #1

3 2
24 18 31
10 8

输出样例 #1

144