2126: dumpling

One of the traditional Chinese foods is the dumpling. Chinese family members and friends will gather to eat dumplings, enjoying the pleasure of family together. In the past, dumplings were, of course, made by hand, and hence families savor the life they possess. Alongside with the rampant development of society and economy, each individual is sort of, let’s say, busy with all kinds of things. Subsequently, less time, or even little, is given to the hand-made-dumpling process, thus engendering the great demand for the retail of dumpling.

And the incidence is that Alice has erected a 24-hour dumpling shop. Its condiment is so special and the price so enchanting that she always gets a lot of orders. However there are surely several rules to be observed, which can be elaborated later.

Only when the time is K o’clock sharp( K = 0,1,2 …. 23) can she make dumplings, and we make the assumption that making cakes takes no time. It’s amazing, ha! Due to the fluctuation of the price of the ingredients and the capricious economy market, there is never lack of booms and busts in each industry. Especially in this case, the cost of a dumpling varies from hour to hour. She can make dumplings when the order comes, or she can make dumplings earlier than needed and store them in a fridgerator. The cost to store a dumpling for an hour is S and the storage span of life of a dumpling is T hours. She now turns to you for help to work out a feasible plan to minimize the cost to fulfill the orders.

For each test case:

The first line includes two integers N and M. N is the total number of orders. M is the number of hours the shop opens.

The next N lines describe all the orders. Each line is in the following format:

month date year H R

It means that on a certain date, a customer orders R dumplings at H o’clock. “month” is in the format of abbreviation, so it could be "Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov" or "Dec". H and R are all integers.

All the orders are sorted by the time in increasing order.

The next line contains T and S meaning that the storage life of a dumpling is T hours and the cost to store a dumpling for an hour is S.

Finally, M lines follow. Among those M lines, the ith line( i starts from 1) contains a integer indicating the cost to make a dumpling during the ith hour . The cost is no more than 10000. Jan 1st 2000 0 o'clock belongs to the 1st hour, Jan 1st 2000 1 o'clock belongs to the 2nd hour, …… and so on.

(0<N <= 2500; 0 < M,T <=100000; 0<=S <= 200; R<=10000 ; 0<=H<24)

The input ends with N = 0 and M = 0.

You should output one line for each test case: the minimum cost. 

1 10
Jan 1 2000 9 10
5 2
20 
20 
20 
10 
10
8
7 
9 
5 
10
0 0

70

“Jan 1 2000 9 10” means in Jan 1st 2000 at 9 o'clock , there's a consumer ordering 10 dumplings.

Maybe you should use 64-bit signed integers. The answer will fit into a 64-bit signed integer.