1623 . 國王烏龜的接駁車
TopCoder
Tags
Description
烏龜國王開放讓百姓去覲見他，舉國上下無一不期待能一睹國王的真面目。
於是，$N$ 隻烏龜便排成一列等著搭上直達皇宮的專車。
然而，搭往皇宮的專車只有$K$班，而每台車重量負荷都一樣是 $M$ 公斤。
現在依序給你每隻烏龜的重量 $w_i$ ，
依序每支烏龜走過來時，車長只能決定叫他立刻上車或是把他踢開，
然後當那隻烏龜上去會超過該台車的負重時那班車就會開走，下一班會立刻過來。
當然國王希望越多隻烏龜能見到他越好，
他想問你，最多能有幾隻烏龜搭上車？
Input Format
第一行包含三個數字$N, K, M$。
第二行有$N$個數字$w_i$，表示從隊伍前端到隊伍末端的烏龜重量。
$1 \leq N, K \leq 2,000$
$1 \leq M \leq 10,000,000$
$1 \leq w_i \leq 10,000$
Output Format
輸出含一個數字，表示最多能讓幾隻烏龜搭上車。
Sample Input 1
5 2 10
5 8 12 3 5
5 8 12 3 5
Sample Output 1
3
Hints
烏龜系列前傳。
Problem Source
原TIOJ1623 / USACO`96
Problem Setter：ATP
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 11 |
| 2 | 1 | 11 |
| 3 | 2 | 11 |
| 4 | 3 | 11 |
| 5 | 4 | 11 |
| 6 | 5 | 11 |
| 7 | 6 | 11 |
| 8 | 7 | 11 |
| 9 | 8 | 12 |