春节到了，BB村里的m个小孩约好一起要到处逛逛要红包。BB村有一条街上住着n个住户，小孩们向他们讨要红包。BB为了讨喜，所有住户都准备了红包，其中第i个住户准备了含有ai金额的红包，但他们不知道会有几个小孩前来讨红包，所以决定直接将红包给上门的小孩让他们自己分。小孩们感情都很好，但不想因为分钱闹得不开心，决定将获得的钱进行平均分配。BB村有个奇怪的习俗，小孩要红包不能出现中断，意寓所有事都一次性搞定。所有给小孩红包的住户必然是连在一起的。小孩们分到了多少钱呢？

不超过100组数据，每组数据先给出两个正整数n,m（m≤n≤1000000）。接下来一行n个正整数ai表示住户i准备的红包（ai<=10000） 

每行一个正整数表示表示每个小孩能分到的最大金额