In the summer lots of people go on vacation to the Mediterranean islands. Ferry boats are one of the preferred means of transportation used to get there, since they allow people to take their cars with them. Ferry boat companies manage a huge number of reservations during the summer and one of the main business concerns is how to optimize ferry cargo.
Boats used by ferry companies can carry lots of weight, practically unlimited, but parking space is strictly limited. In general ferry companies use different kinds of boats to serve as the means of transportation, each one differing in the amount of centimeters of parking space. To help the ferry management process, each ferry reservation includes the length of the vehicle that will be transported. Reservations are handled on a first come, first served basis. In order to optimize cargo, ferry companies decide upon which type of boats will be used depending on the amount of parking space wasted in transporting the cars, i.e., the amount of unused parking space, regardless of how many boats have to be used throughout the summer. Cars are parked so close to each other that no space is left between them. Ideally the parking space is completely used up, which means there is no space waste at all.
You have been hired by a ferry boat company that is interested in finding out what is the minimum amount of parking space wasted in all ferry transports that depart from the same origin port and that are directed to the same destination port, during all summer, given the parking capacity of all boats that can be used and the order and length of the vehicles that will be transported. This company in particular operates with an unlimited fleet of boats since they reuse their own repeatedly and rent boats of other companies whenever necessary. There is always at least one type of boat that can carry any kind of car.
For the sake of illustration consider that you are given two types of boats, one with capacity 400 and the other with capacity 800, and a sequence of 5 cars all with length 300. The minimum waste to transport this sequence is 500, obtained, for example, transporting the first car in a boat of capacity 400 (waste 100), transporting the second and third cars in a boat of capacity 800 (waste 200), and transporting the fourth and fifth cars in a boat of capacity 800 (waste 200) as illustrated in the figure below.
Write a program that, given the distinguished set (all distinct values) of capacities of the types of boats that can be used (each type having an unlimited available fleet), and the sequence of lengths of the cars that will be transported, computes the minimum amount of parking space wasted in transporting the cars on the boats, without ever exceeding the parking capacity. The amount of parking space wasted is given by the sum of all unused centimeters in all boat travels necessary to transport all the cars.
The first line contains an integer value that specifies the number of boats B followed by an integer value that specifies the number of cars C, separated by a single space. The following B lines contain B distinct integer values, each one corresponding to a boat parking space capacity (in centimeters): S1, …, SB. Then, the following C lines contain C integer values, each one specifying the length of a car (in centimeters): L1, …, LC. The order in which the cars are served is given by the ordering of the lengths in the input. At least one of the boat capacities is greater than or equal to any car length: max(L1, …, LC) ≤ max(S1, …, SB).
The output consists in a single line containing an integer value W that identifies the minimum amount of parking space wasted (in centimeters).
|1 ≤ B ≤ 100||Number of ferry boats|
|1 ≤ C ≤ 100,000||Number of cars|
|50 ≤ S1≤ i ≤ B ≤ 1,000||Boat capacities|
|50 ≤ L1≤ i ≤ C ≤ 1,000||Car lengths|
|0 ≤ W < 50,000,000||Parking space waste|
2 5 400 800 300 300 300 300 300
3 3 400 800 600 300 400 200
MIUP'2012, 20 de Outubro, DCC/FCUP
This document was translated from LATEX by HEVEA.