HZNUOJ

生猴子系列2

Tags:
Time Limit:  2 s      Memory Limit:   32 MB
Submission:306     AC:79     Score:96.88

Description

mwycjc生猴子,他们的任务是在n天生出m只猴子。但是能力有限,他们需要找sjy代孕猴子,sjy每天帮他们代孕的价格是不同的,并且每天最多代孕k只猴子。(理想条件下,一天生若干只猴子)。找出最少的费用完成任务。

Input

第一行给出T,代表T组测试数据。

每组测试数据中,第一行三个数据分别是n0<n<100)和m1<m<100000),k1<k<1000),接下来两行,第一行有n个数据代表从第一天到第n天,mwy每天所能生的猴子数num0 < num < 500),第二行有n个数据代表从第一天到第n天,sjy代孕所需费用。

Output

如果可以完成任务,则输出最少需要的费用找sjy代孕;

否则输出“cjc fighting!!!.

Samples

input
1 3 15 1 7 2 3 1 3 2
output
6

Author

WANG, Xiaoan