#P2212. 此题有毒,请勿轻易尝试。

此题有毒,请勿轻易尝试。

某日,GLaDOS终于受不鸟cszdlt的愚蠢,然后他对cszdlt说:,cszdlt说:。cszdlt被嘲讽后心里很不爽,决定去找妹纸玩。那么问题来了,cszdlt认识n个妹子,每个妹子都有自己的智商值Z和相貌值X。他能挑选一些妹子一起玩,但cszdlt有一个智商容纳值m,他挑选的妹子的智商和不能超过m。现在cszdlt想知道前k个第i大的相貌值(i=1.....k)与对应的智商值

你以为结束了吗?。。。。就在cszdlt自信满满的计算的时候,妹子TEMP问了个他问题:TEMP想在k个值中选择c个值,使得∑(第j大的相貌值)/∑(对应的智商值){其中j是被选出的编号}达到最大值;

Input

第一行是测试数据组数T,(T<10)。每组例子有4个整数n,m,k,c;(1<=n<=100,1<=m<=1000,1<=c<=k<=50)。接下来有2行,第一行是妹子的相貌值,第二行是对应妹子的智商值。保证所有X和Z都小于int型范围。

Output

每组样例输出一行,输出(∑(第j大的相貌值)/∑(对应的智商值))的最大值*100后四舍五入到整数。

Sample Input

1
5 10 13 3
1 2 3 4 5
5 4 3 2 1

Sample Output

300

HINT

样例前个13相貌值为14 12 11 10 9 8 7 6 5 4 3 2 1;
对应得智商值为  10 6 7 8 3 4 5 6 1 2 3 4 5
ans=(9+5+4)/(3+1+2)*100=300

Source