5. 浇花系统
题目描述
有n棵植物,排成一排,从左到右的编号分别为:1,2,3,......,n ;n颗植物所需的水量分别为:w1,w2,w3,......wn 。小丁为植物设计了一套浇水系统。
浇水系统:每次会将连续的L棵植物分别浇1份水。每棵植物可以被重复浇水,如果当前植物已经满足所需水量,系统会将多浇的水排到水池中。
请计算浇水系统最少要浇多少次才能满足所有植物所需水量,以及排到水池的水量。
例如:n=4,L=3;4棵植物所需要的水量分别为1、1、3、2,浇水系统每次会将连续的 3 棵植物分别浇上1份水。以下是浇水次数最少的一种方式:
• 第一次:将第1、2、3 棵植物分别浇上1份水,浇水后4棵植物所需水量为0、0、2、2;
• 第二次:将第 2、3、4 棵植物分别浇上1份水,浇水后4棵植物所需水量为0、0、1、1,由于第2棵植物已经满足所需水量,所以系统会将此次多余的1份水排到水池;
• 第三次:将第 2、3、4棵植物分别浇上1份水,浇水后4棵植物所需水 量为0、0、0、0,此次系统也会将第2棵植物多余的1份水排到水池;所以,浇水系统最少需要浇3次,并且将多余的2份水排到水池。
输入描述
第一行输入两个整数n、L(1 ≤ L ≤ n ≤ 1000),分别表示植物的数量和浇水系统每次连续浇灌的植物数量,整数之间以一个空格隔开。
第二行输入n个整数w(0 <= w; <= 1000) ,分别表示编号 1~n 的植物所需的水量,整数之间以一个空格隔开。
输出描述
输出两个整数,分别表示浇水系统最少的浇水次数,以及排到水池的水量,整数之间以一个空格隔开。
样例输入
4 3
1 1 3 2
样例输出
3 2