Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
86 - ZOJ Monthly, January 2010 - B
Attack!

Time Limit: 1 Second      Memory Limit: 32768 KB

Nevermore the Shadow Fiend is among the most powerful heroes in the game Defense of the Ancients. Indeed, Zhejiang University is famous for one especially good Shadow Fiend player. However, to master this hero is not so easy, for starters, it's enlightening to learn how to maximize the damage output of Shadow Fiend when chasing down enemies. Shadow Fiend has three powerful skills.

  • ShadowRaze: This skill actually consists of N similar skills, each dealing D damage to the enemy in the ranges [xi, yi], 1 <= i <= N.
  • Necromastery: This skill enables Shadow Fiend to gather the souls of the enemies that he had killed.
  • Requiem of Souls: Suppose the enemy is X distance far from Shadow Fiend and had gathered P souls from the enemy, this skill deals M*P/X^2 damage to the enemy.

Now, suppose an enemy's distance is initially K from Shadow Fiend and Shadow Fiend wants to kill the enemy. The enemy is trying to escape at speed V, and for simplicity we suppose this Shadow Fiend will not move but just use his techniques to kill the enemy. Alas, there are restrictions to Shadow Fiends skills, they cannot be used instantaneously. For each of the N ShadowRaze skills, there is T1 time to prepare and after which the skill can be used. For Requiem of Souls the time to prepare is T2. The techniques must be used right after the preparation time, you can not prepare then wait some time to use it.

You are to determine the maximum damage Shadow Fiend can do to the enemy.

Note:

Since the skills have rather long Cooldowns, each of the N ShadowRaze attack can be used only once, and Requiem of Souls can be used once. Also, for the N ShadowRaze attacks, it would make no sense if one attack's range covers another, which would render imbalance in the game. Thus, there is no i and j that xi < xj and yi > yj.

Input

The first line is the number T(1 <= T <= 100), the number of test cases. T test cases follow and are of the following format: The first line contains integers: N(1 <= N <= 1000), D(1 <= D <= 100), M(1 <= M <= 100), P(0 <= P <= 100), K(0 <= K <= 100), V(0 < V <= 10), T1(0 < T1 <= 10), T2(0 < T2 <= 10). Then follows N lines, each containing two integers xi and yi,1 <= i <= N,both numbers are within 10000.

Output

For each test case output one integer, the maximum damage Shadow Fiend can do to the enemy. For Requiem of Souls, use the expression M*P/(X*X) to compute the integer value of the damage, where X is the distance when Requiem of the souls is used.

Sample Input

2
1 100 100 100 0 10 1 1
10 15 
1 100 100 100 0 10 1 1
20 30 

Sample Output

125
200

Author: SONG, Yu
Source: ZOJ Monthly, January 2010
Submit    Status