$n$ 名音乐系学生即将在音乐厅进行排练。在一次排练轮次中，每位学生将按从学生 $1$ 到学生 $n$ 的顺序依次进行一次表演。学生 $i$ 的表演时长为 $d_i$。当最后一名学生的表演结束后，新的排练轮次会立即开始，并从学生 $1$ 的表演重新开始。

每天，音乐厅开放的固定时长为 $p$。如果在任何时刻，下一位学生的表演无法在音乐厅关闭前完成，则当前排练轮次中剩余的所有表演都将顺延至第二天。

在 $k$ 天内，该班级总共能完成多少次完整的排练轮次？

威尔独奏厅，卡内基音乐厅，摄影：Nat Welch

输入格式

第一行包含三个整数 $n, p, k$ ($1 \le n \le 2 \cdot 10^5, 1 \le p, k \le 10^9$)。接下来的 $n$ 行，每行包含一个整数。第 $i$ 行给出了 $d_i$ ($1 \le d_i \le p$)。

输出格式

输出在 $k$ 天内该班级能完成的完整排练轮次数量。

样例

样例输入 1

3 9 5
1
2
3

样例输出 1

7

样例输入 2

4 10 5
3
2
4
6

样例输出 2

2

样例输入 3

3 10 2
5
6
7

样例输出 3

0