hosonagaitokoro

Takahashi decided to go sightseeing in New York with Apple. Takahashi didn't have any particular hope for sightseeing, but due to Sachika-chan's enthusiastic invitation, he decided to go sightseeing in the "hosonogai place" as shown in the map below.

Google Maps-(C) 2012 Google

This "horizontal place" is very elongated and can be regarded as a straight line. In addition, there is a start point at one end and a goal point at the other end, and several tourist carriages are running from the start point to the goal point. This carriage operates according to the following rules.

• There are n carriages, and all carriages start from the starting point and proceed to the goal point.
• The size of the carriage can be ignored in all of the following cases:
• Since it is difficult to change the speed on the way, all carriages travel at a constant speed of Si (Si is an integer of 1 or more) per 1 km.
• The carriages have a set departure order, and you must follow this order. However, there is no particular rule regarding the order in which you will arrive at the goal point.
• Multiple carriages cannot depart from the starting point at the same time, and if one carriage departs, there must be at least one minute before the next carriage departs.
• The goal point is wide enough that any number of carriages can arrive at the same time. Also, the carriage that arrives at the goal point stops there and stays at the goal point all the time.
• Since the "Hoso Nagai" is very long and narrow, basically two carriages cannot be lined up in the same place. However, there are special "slightly wide areas" in m, where up to two can be lined up, allowing one carriage to overtake another.

In addition, the following restrictions are satisfied for the above-mentioned "horizontal place" and "slightly wide place".

• There is a straight line from the start point to the goal point, and the distance is (dist) km (dist is an integer greater than or equal to 1).
• There are m "slightly wide areas" somewhere from the start point to the goal point, none of which overlap the start point and goal point. Also, each "slightly wide area" is exactly (Di) km (Di is an integer greater than or equal to 1) from the starting point.

Upon hearing this, Mr. Takahashi adjusted the departure time of the carriage while observing the rules of carriage operation described above, so that the time required from the departure of the first carriage to the arrival of all the carriages was reduced. I found out that I could make it smaller. In order to know the result of Mr. Takahashi, the number of carriages n, the parameter Si regarding the speed of each carriage, the total number of "slightly wide places" existing on the "horizontal place" m, each "slightly wide place" Given the distance Di from the starting point, it's your job to write a program that finds the minimum amount of time it takes for all carriages to arrive after the first carriage departs. In addition, Sachika-chan fully enjoyed sightseeing in "Hosonagai-ko", but Takahashi-kun only muttered "It was hospitable ..." after this sightseeing.

Constraints

1 ≤ dist ≤ 100000000 (108) 1 ≤ n ≤ 5 0 ≤ m ≤ 5 1 ≤ Si ≤ 100 0 <Di <dist If i ≠ j then Di ≠ Dj All numbers appearing in the input are integers.

• If i <j, the i-th carriage must depart at least 1 minute earlier than the j-th carriage

Input

The input format is as follows.

dist n S1 S2 .. Sn m D1 D2 .. Dm

• dist represents the distance (km) from the start point to the goal point
• n represents the number of carriages departing from the starting point
• Si represents the speed of the carriage, and the i-th departing carriage represents 1 km in (Si) minutes.
• m represents the total number of "slightly wide areas"
• Di represents the distance (km) from the starting point to each "slightly wide area".

Output

Output the minimum time it takes for all carriages to arrive in one line after the first carriage departs. The unit is minutes.

Examples

Input

100 2 1 2 0

Output

201

Input

100 2 2 1 0

Output

200

Input

100 3 2 1 1 1 50

Output

200

Input

100 4 3 1 1 3 2 40 60

Output

421

inputFormat

input are integers.

• If i <j, the i-th carriage must depart at least 1 minute earlier than the j-th carriage

Input

The input format is as follows.

dist n S1 S2 .. Sn m D1 D2 .. Dm

• dist represents the distance (km) from the start point to the goal point
• n represents the number of carriages departing from the starting point
• Si represents the speed of the carriage, and the i-th departing carriage represents 1 km in (Si) minutes.
• m represents the total number of "slightly wide areas"
• Di represents the distance (km) from the starting point to each "slightly wide area".

outputFormat

Output

Output the minimum time it takes for all carriages to arrive in one line after the first carriage departs. The unit is minutes.

Examples

Input

100 2 1 2 0

Output

201

Input

100 2 2 1 0

Output

200

Input

100 3 2 1 1 1 50

Output

200

Input

100 4 3 1 1 3 2 40 60

Output

421

样例

100
4
3
1
1
3
2
40
60

421