BitTorrent

Time limit2sMemory limit128 MB

Summary

Choose the most files whose covering fixed-size pieces fit in the bandwidth budget, where a piece shared by files is paid once.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

BitTorrent is a protocol for transferring large files over a peer-to-peer network. Unlike the centralized client-server architecture, where client nodes ask central servers for resources, every node here acts as both a client and a server. Users form a group of hosts that download files from each other and upload to each other at the same time.

The whole package of files, called a torrent, is cut into pieces the way the figure shows. A 10MB package might be cut into exactly ten 1MB pieces, or into exactly forty 256KB pieces. As soon as a host (a peer) receives a new piece, it becomes a source of that piece for other hosts that want it. Pieces usually arrive out of order, and each host rearranges them into the original order. Every host decides on its own which pieces to download. Inside a single torrent all pieces have the same size, except the last piece, which may be smaller.

You want to download a package of files, but you are close to your monthly Internet usage limit and you do not want to wait for next month. With the bandwidth you have left, you want to end up with as many complete files as possible.

A piece cannot be split, so downloading one means downloading all of it. To own a file you have to download every piece that holds any part of that file, and a piece shared by several files is downloaded once. The files are concatenated in the order given in the input, and the result is cut from the front into pieces of $P$ KB.

Find the maximum number of files you can download completely with the bandwidth left.

Input

The input contains multiple test cases. Each test case starts with three space-separated integers $N$ , $P$ and $L$ . $N$ is the number of files in the torrent ( $1 \le N \le 3000$ ), $P$ is the size of a piece in KB ( $1 \le P \le 1000$ ), and $L$ is the number of kilobytes left in your monthly Internet usage limit ( $1 \le L \le 10^6$ ). The second line of a test case contains $N$ space-separated positive integers not exceeding 100,000, where the $i$ -th integer is the size in KB of the $i$ -th file in the torrent. The input ends with the line 0 0 0, which is not processed.

Output

For each test case, print on one line the maximum number of files that can be downloaded completely. If no file can be downloaded completely, print 0.

Examples1

Example 1

Input

3 3 13
5 5 7
7 2 16
6 11 3 3 8 1 8
0 0 0

Expected output

2
4