题目描述

阿兔喜欢玩杀戮尖塔，现在正在扮演铁甲战士爬塔！

铁甲战士现在手上有 $n$ 张攻击牌且有 $m$ 点能量，每一张牌需要消耗 $x$ 点能量，打出后会造成 $y$ 点伤害，每一张牌最多只能使用 $z$ 次。

铁甲战士想要在一轮内击败剩余血量为 $h$ 的 BOSS。如果总伤害能够大于等于 BOSS 血量，则视为成功击杀。

你需要求出能够击杀 BOSS 的最小能量消耗。如果无论如何都无法击杀，则输出 -1。

输入格式

第一行三个整数 $n, m, h$。

第二行 $n$ 个整数，表示每张牌的能量消耗 $x$。

第三行 $n$ 个整数，表示每张牌的伤害 $y$。

第四行 $n$ 个整数，表示每张牌的数量 $z$。

输出格式

一个整数，表示击杀 BOSS 的最小能量消耗，无法击杀则输出 -1

3 5 25
1 2 1
7 12 18
1 3 1

2

3 5 25
1 10 1
6 12 18
1 3 1

-1

数据范围

• 对于 $10\%$ 的评测用例，$n, m, h≤20$，$x,y≤10$，$z=1$;
• 对于 $30\%$ 的评测用例，$n, m, h≤200$，$x,y,z≤100$;
• 对于所有评测用例，$1 \leq n, m, h≤2000$，$1≤x,y,z≤10^{9}$。