Problem Statement

You are given a sequence of positive integers $A=(A_1,A_2,\cdots,A_N)$ of length $N$.

Consider dividing this sequence into $K$ non-empty contiguous subsequences. Among these $K$ contiguous subsequences, the number of ones whose sum of elements is at least $S$ will be called the score. Find the maximum value of the score.

Constraints

• $1 \leq K \leq N \leq 250000$
• $1 \leq A_i \leq 10^9$
• $1 \leq S \leq 10^{15}$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N K S
A_1 A_2 \cdots A_N

Output

Print the answer.