TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

78.3% (36/46)

Submission's AC Ratio

44.0% (70/159)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9