Problem: Tickets

Want to try solving this problem? You can submit your code online if you log in or register.

Tickets

Input File: ticketin.txt
Output File: ticketout.txt
Time Limit: 1 second

Amanda is travelling to the land of Ruritania to research specimens of local insects. In her time there, she will need to travel between different cities in Ruritania. There are two types of tickets in Ruritania. Each ticket has some cost and is valid for travel on any train in Ruritania for a given number of days, starting on the day it is bought.

Amanda will be in Ruritania for a while, and knows in advance which days she will be travelling. She wants to know which tickets to buy and when, so that the total money she spends on train tickets is minimised.

Consider the following example. Suppose that Ruritania has the following two tickets:

Cost	Validity
$4	3 days
$7	5 days

Amanda's itinerary around Ruritania has her travelling on days 1, 2, 4, 6, 8, 13 and 16.

In this scenario, Amanda could choose to buy a 3-day ticket on days 1, 4 and 8 and a 5-day ticket on day 13. This would cover all the days she wishes to travel, and would cost her $4 + $4 + $4 + $7 = $19. A cheaper way to travel is to purchase a 3-day ticket on day 1, and two 5-day tickets on days 4 and 13. These also cover all the days she wishes to travel and costs her only $4 + $7 + $7 = $18. This is in fact the cheapest she can travel for under these circumstances.

Your task is to write a program that given the cost and validity of tickets available and Amanda's travel schedule, determines the smallest amount of money Amanda would need to spend on tickets.

Constraints

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

0 ≤ D ≤ 10,000, where D is the number of days on which Amanda needs to travel.
The cost of each ticket will be at least $1 and at most $1000.
The validity of each ticket will between 1 and 100 days, inclusive.
Amanda's journey will last at most 100,000 days.

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large - in particular:

For 50% of the available marks, 1 ≤ D ≤ 20.

Input

Your program should read from the file . The first two lines of the file describe the two tickets. Each of these lines contains two integers separated by a space - the cost of a ticket in dollars and its validity in days, respectively. The third line will be the integer D, the number of days on which Amanda wishes to travel.

The following D lines of the file each contain a single integer, specifying which days Amanda wishes to travel. Days are numbered from 1 and will appear in sorted order. No day will appear twice.

Output

Your program should write to the file . This file should consist of a single integer: the minimum amount Amanda needs to spend so that she can make all her journeys in Ruritania.

Sample Input

Sample Output

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.