Description

You have just inherited the rights to $N$ ($1\le N\le20$) unreleased songs recorded by the popular "Raucous Rockers" band. You plan to select some of them to release on $M$ ($1\le M\le20$) CDs. Each CD can hold at most $T$ ($1 \le T\le20$) minutes of music, and a song cannot be split across two CDs. You may use fewer than $M$ CDs.

Unfortunately, you are a classical music fan and do not know how to judge their artistic value. So you decide to choose according to the following rules:

• The songs must appear on all CDs in the order they were composed, that is, the last song on disc $i$ must have been composed earlier than the first song on disc $i+1$.
• The number of selected songs should be as large as possible.

Input Format

The first line: three integers $N, T, M$.

The second line: $N$ integers, the length of each song, in order of composition.

Output Format

A single integer, the maximum number of songs that can fit on $M$ CDs.

4 5 2
4 3 4 2

3

Hint

Translation comes from NOCOW.

USACO Training Section 3.4.

Translated by ChatGPT 5