IOI Photos

Shaborz, Hoidin, Alssein, and Ayan, members of the Olandica IOI team, attended their fall-semester classes on the very day they returned from IOI Athens 2004. During their stay in Athens they took many pictures at different places and occasions such as Hydra island, the opening ceremony, the closing award ceremony, and the city of Athens. Excited by their first university experience, they forgot about the pictures until the midterm recess, which happened to coincide with the ACM Regional Contest. Now they want to make prints and each build his own IOI album.

There are several film rolls, and each roll contains photos of just a single place or occasion. More than one roll may contain pictures of the same place or occasion. Each roll holds up to 36 negatives, numbered from 1 to 36. The team members and their friends order photo prints. Shaborz collects all the orders and makes the following deal with a printing shop:

• Printing one single photo costs $S$ Rials.
• Printing all photos of a single roll costs $R$ Rials.
• Printing all photos of all rolls in one order costs $A$ Rials.

Given the list of orders, minimize the overall printing cost. A roll is identified by its (place name, roll number) pair. To reach the minimum cost, Shaborz is allowed to print more photos than required.

The first line of the input contains a single integer $t$ ($1 \le t \le 20$), the number of test cases.

Each test case starts with one line of four integers $N$ ($1 \le N \le 100$), $S$, $R$, and $A$: the number of orders and the costs of a single print, of one whole roll, and of all rolls respectively.

Then follow $N$ lines, each representing one order from a client (a team member or friend). An order line contains several items separated by blanks. Each item has the form PlaceName:RollNo:FromPhoto..ToPhoto.

• PlaceName is a string of at most 100 characters (case sensitive).
• RollNo selects the desired roll among the rolls of that place and is between 1 and 10 inclusive.
• FromPhoto and ToPhoto give the range of photos to print, with 1 ≤ FromPhoto ≤ ToPhoto ≤ 36.

You may assume there are at most 20 places. If only a single photo of a roll is required, the item may be shortened to PlaceName:RollNo:PhotoNo. All costs are non-negative integers.

For each test case, output one line with a single integer: the minimum cost of printing all photos in the original order set.