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:
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.
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:
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:
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.
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.
4 3 7 5 7 1 2 4 6 8 13 16
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.