该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 L 在工厂的流水线上负责把产品装箱。流水线上共有 n 个产品依次流过，编号 1 ~ n，第 i 个产品的重量为 w[i]。流水线旁有一个收集箱，它同时受到两个限制：

• 重量上限 C：箱内所有产品的重量之和不得超过 C；
• 数量上限 m：箱内产品的数量不得超过 m。

初始时收集箱为空。小 L 按照产品流过的顺序依次处理第 1, 2, ..., n 个产品。处理第 i 个产品时：

1. 若把产品 i 放入收集箱后，箱内产品的重量之和不超过 C，并且数量不超过 m，则把产品 i 放入收集箱；
2. 否则，先把收集箱中已有的产品全部打包运走（这一次打包称为一次装运，其总重量为箱内所有产品的重量之和），此时收集箱为空；然后再把产品 i 放入收集箱。保证 w[i] ≤ C 且 m ≥ 1，因此产品 i 一定能放入空的收集箱。

所有产品处理完毕后，如果收集箱中仍有产品，还需要把它们全部打包运走，作为最后一次装运。

小 L 想知道：一共进行了多少次装运？其中最重的一次装运中，产品的总重量是多少？

输入格式

从文件 plant.in 中读入数据。

第一行包含三个正整数 n, C, m，分别表示产品的数量、收集箱的重量上限和数量上限。

第二行包含 n 个正整数 w[1], w[2], ..., w[n]，相邻整数之间以单个空格分隔，按流过流水线的顺序依次表示每个产品的重量。

输出格式

输出到文件 plant.out 中。

输出一行包含两个整数，用一个空格分隔，分别表示装运的次数，以及最重的一次装运中产品的总重量。

6 10 3
2 3 4 1 5 6

3 9

解释

• 前三个产品重量为 2, 3, 4，依次放入收集箱后箱内有 3 件产品、总重 9，恰好不超过两个上限；
• 第 4 个产品重量为 1，虽然 9 + 1 = 10 不超过重量上限，但放入后会有 4 件产品，超过数量上限 3，因此先把 2, 3, 4 打包运走（第 1 次装运，总重 9），再把重量为 1 的产品放入；
• 第 5 个产品重量为 5，放入后总重 1 + 5 = 6 ≤ 10、共 2 件产品，可以放入；
• 第 6 个产品重量为 6，若放入则总重为 12 > 10，因此先把 1, 5 打包运走（第 2 次装运，总重 6），再把重量为 6 的产品放入；
• 全部产品处理完毕后，收集箱中还有重量为 6 的产品，进行第 3 次装运，总重 6。

共装运 3 次，最重的一次总重量为 9。

4 100 10
1 2 3 4

1 10

解释

所有产品都能放入同一个收集箱：总重 1 + 2 + 3 + 4 = 10 ≤ 100，共 4 件产品 ≤ 10。处理完毕后只有最后一次装运，总重 10。

5 6 2
3 3 3 3 3

3 6

解释

• 产品 1, 2 依次放入，此时总重 3 + 3 = 6 ≤ 6、共 2 件产品 ≤ 2，恰好达到两个上限；
• 产品 3 若再放入则超重，因此先把产品 1, 2 打包运走（第 1 次装运，总重 6），再放入产品 3；
• 产品 4 放入后总重 6、共 2 件产品；
• 产品 5 若再放入则超重，因此先运走产品 3, 4（第 2 次装运，总重 6），再放入产品 5；
• 最后把产品 5 打包运走（第 3 次装运，总重 3）。

共装运 3 次，最重的一次总重量为 6。

样例 4、样例 5

见选手目录下的 plant/plant4.in 与 plant/plant4.ans，该样例满足 n ≤ 50 的限制。

见选手目录下的 plant/plant5.in 与 plant/plant5.ans，该样例满足 n ≤ 10^5 的限制。

数据范围

对于所有测试数据，保证：1 ≤ n ≤ 10^5，1 ≤ w[i] ≤ C ≤ 10^9，1 ≤ m ≤ 10^5。