3981：Sacred Warrior

Sacred Warrior is a hero in DotA and his name is Huskar. The Sacred Warrior’s abilities revolve around shortening his own lifespan to spear his foes to burinng pieces.When we control the Sacred Warrior , we always want to give our enemies the most damage.So to simplify the problem,let’s consider the Sacred Warrior’s two skills as below:

(1) Burning Spear

When the Sacred Warrior use the Burning Spear to attack his enemy, follow things will happen in order in the current second:

1.the enemy gets physical hurt by a normal attatk.

2.if the enemy’s burning degree BD is greater than zero,the enemy will gets BD*FI damage points.(at the beginning,the enemy’s burning degree is zero).

3.the enemy’s burning degree +1.

4.the remanent burning time become 6.

5.the Sacred Warrior’s HP decrease by D. The Sacred Warrior can not kill himself(don’t ask me why),that is,when the Sacred Warrior’s HP is less than or equal to D, the Sacred Warrior can not use Burning Spear!

When the Sacred Warrior use a single normal attack instead of Burning Spear, follow things will happen in order in the current second:

1.the enemy gets physical hurt by the normal attack.

2.if the enemy’s burning degree BD is greater than zero,the enemy will gets BD*FI damage points.(at the beginning,the enemy’s burning degree is zero).

3.the remanent burning time decrease by 1.

4.if the remanent burning time is zero, then the enemy’s burning degree become zero.

(2) Berserk’s blood

The Sacred Warrior’s base attack is A.

Whenever the Sacred Warrior’HP reduce R ,his attack will increase U, it means the Sacred Warrior will get ((HS-HC) / R)*U extra attack.(round down for division, hs is the original HP and the hc is the current HP).

The normal attack NA is the sum of base attack and extra attack.

The enemy has a defence degree DEFi and it change every second(the reason is complicated,such as Weave,Meld,Gush,Natural Order,Mekansm and so on).Whenever the enemy is attacked by a normal attack(a single normal attack or the first part of Burning Spear), if the enemy’s defence degree is greater than the normal attack, the enemy won’t get any physical hurt(but the burning effect is still effective), otherwise the enemy will get NA-DEFi damage.(NA is the current normal attack and the DEFi is the current defence degree).

Every second The Sacred Warrior can choose using a single normal attack or Burning Spear to attack the enemy. But in order to make the most damage and lose too much HP is obviously not wise. So we use a evaluation function F=C - (HS-HE)*P to evaluate the fight. (hs is the original HP and the he is the HP after last second, C is the total damage he cause).Can you find the maximal F ?

The first line contains a single positive integer N( N <= 20 ), indicates the number of test cases.

For each test case:

The first line contains eight integers T , HS , A , R , U , D , FI , P , T is the total time in seconds and the others is as described above.

The second line contains T integers , the i-th integer is the defence degree DEFi in i-th second.

0< T < 200 , 0< HS < 100 , 0 < A < 5000 , 0< R < HS , 3<= D <= 10 , 0 <= U , FI , P <1000

0 <= DEFi <3000

For each test case, print a line containing the test case number (beginning with 1) and the maximal F.