SEUG - Seetha’s Unique Game

no tags 

There was once a little girl named seetha who loves to play little tricky games. Once she was playing with stones, noticed a rectangular glass box with some water fill in it. She invented a game with a that box. She wants to share the rules of the game with you all. The rules are as follows:

You will be given length, width and height of the rectangular box and the amount of water in it. You will also be given the number of stones she has. The weight of stones will be given such as w1,w2,w3, …, wn and each weight will resemble how much water level it can increase in units.

If you continuously put stones in that box, at a certain level the water will spill out from the glass box. You have to determine the minimum number of stones needed.

Input

First line of input contains number of test cases T (T ≤ 10).

Second line of input contains three numbers 1 ≤ a, b, h ≤ 1000 and 1 ≤ w ≤ 1000 representing the length, height and width of the box and the amount of water filled in the glass box.

In the Third line you will be given 2 ≤ N ≤ 1000 which represents the number of stones she has. Next line of input contains N space separated numbers 1 ≤ wi ≤ 100 which resemble the weight of each stones.

Output

Print the minimum number of stones needed according to problem statement.

Example

Input

2
5 3 10 2
6
5 8 1 4 3 2
12 6 22 8
9
2 5 4 2 3 1 2 3 1

Output

2
4

hide comments
vishalsingh17: 2017-12-31 08:04:12

AC in one go !!

sonuverma: 2017-12-30 14:15:48

read statements carefully :-)


Added by:Sarwar
Date:2017-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All