Description

Shaborz, Hoidin, Alssein, and Ayan, members of the Olandican IOI team attended the Fall semester classes the same day they returned from IOI, Athens 2004. During their stay in Athens, they took several pictures in different places and occasions like Hydra island, opening ceremony, closing award ceremony, and city of Athens. But, being excited with their first university experience, they forgot about the pictures until the midterm recess, which has coincided with the ACM Regional Contest days. They now want to make prints of the pictures and each of them makes his own IOI album.

There are several negative rolls, and each contains photos of just a single place or occasion. There may be more than one roll, containing pictures from the same place or occasion. Each roll may have 36 negatives, numbered from 1 to 36. The team members and their friends want to order photo prints. Shaborz is to collect all orders and collects a fixed amount of money per each photo print. He makes a deal with a photo printing shop as follows and saves a good sum of money for himself. Shaborz pays S Rials for each single print, but printing all photos of a single role costs him R Rials, and printing all photos from all rolls in one order costs A Rials. Shaborz is provided with a list of orders, and you are to minimize the overall printing cost. Note that to have the minimum overall cost, Shaborz is allowed to print more photos than required.

Input

The first line of the input contains a single integer t (1 <= t <= 20) which is the number of test cases in the input. Each test case starts with one line containing four integers: N (1 <= N <= 100), the number of orders, S, R, and A, the costs of a single print, all prints from one roll, and all prints of all rolls respectively. Then follows N lines, each representing an order from one of the clients (team members and their friends). An order line contains a number of items separated by blank characters. Each item is of the form PlaceName : RollNo : FromPhoto..ToPhoto. PlaceName is the name of a place which is a string of at most 100 characters (case sensitive). RollNo specifies the desired roll among several rolls for the PlaceName and is between 1 and 10 inclusive. FromPhoto and ToPhoto are two numbers specifying the range of photos to be printed from the specified roll (1 <= FromPhoto <= ToPhoto <= 36). You may assume there are at most 20 places. If there is only a single photo required from a roll, the format may be simplified as PlaceName : RollNo : PhotoNo. All costs are non-negative integers.

Output

For each test case, there should be one line containing one integer indicating the minimum cost for printing all photos of the original order set.

1
2 15 100 400
Hydra:2:1..3 Athens:1:12
Delphi:1:4..5 Athens:3:20

105

Source

Tehran 2004