It's high noon!
Jiubei loves playing Overwatch even if it is a long time since the last update. Now he is using a damage skill to kill enemies.
The skill will damage all enemies simultaneously and the damage is determined by the time Jiubei charges this skill. The skill has a charging period division number , and two damage increase numbers . If he charged for seconds, the damage is calculated as follows:

• If , the damage is .
• Otherwise, the damage is

Jiubei has enemies, and the -th enemy's health is .
Please tell Jiubei how long it takes to charge his skill to kill all of his enemies.Note that the skill can only be used once.
Additionally, an enemy is killed if and only if his health is not greater than the damage he/she take.

The first line contains a single integer  --- the number of test cases.
The first line of each test case contains four integers  --- the number of enemies, the number of charging period division, the numbers of damage increase respectively.
The second line of each test case contains  integers  --- the health of enemies.

For each test case, output a single integer in a line, indicating the minimum time Jiubei needs to charge his skill to kill all enemies.

2
3 2 4 3
1 2 5
3 2 4 3
1 5 21

2
7