Background

继陶陶摘苹果

又是一年秋天,陶陶家的果树又结果了....

Description

今年树上结了 $n$个苹果,第 $i$个苹果的价钱和高度为 $a_i,\ b_i$ 他有一个高度为 $s$的板凳,重量为 $x$. 当他够不到时他就会拿起板凳走到第 $i$个果树下面移动的时候会消耗体力 ($P$)

摘一个苹果会赚 $a_i$ 块,问最大可以转多少钱

Format && Input

$n,\ P, \ x$

$a_1,\ a_2,\ a_3,\cdots a_i$

$b_1,\ b_2,\ b_3,\cdots b_i$

$s,\ x$

所有输入均为实数,

$0\le \ n,P,x \le 20$

$0\le \ s, \ x \le 100$

$0\le \ a_i \le 1000$

Output

最大可以转多少钱

Samples

3 10 1
1 15
3 2
10 3
2 10

10

Limitation

1s, 1024KiB for each test case.