ほそながいところ
高橋君は苹果(りんご)ちゃんとニューヨークを観光することになりました。 高橋君は観光するところに特に希望はなかったのですが、苹果ちゃんの熱烈な誘いにより、以下の地図にあるような"ほそながいところ"を観光することに決まりました。
この"ほそながいところ"はとても細長く、直線とみなすことができます。また、"ほそながいところ"には片方の端にスタート地点が、もう片方の端にゴール地点があり、スタート地点からゴール地点へ向けて何台かの観光用の馬車が走っています。この馬車は以下のようなルールに従って運行されています。
- 馬車はn台あり、すべての馬車はスタート地点から出発してゴール地点まで進みます。
- 以下のすべての場合において馬車の大きさは無視できます。
- 途中で速度を変更することが難しいため、すべての馬車は馬車はそれぞれ1kmあたりをSi(Siは1以上の整数)分の等速で進みます。
- 馬車には出発する順番が定められており、この順番を守らなければなりません。ただし、ゴール地点に到着する順番について特に決まりはありません。
- 複数の馬車はスタート地点を同時に発車することはできず、ある馬車が発車すれば次の馬車が発車するまでに1分以上間をあけなければなりません。
- ゴール地点は十分に広いため、何台の馬車が同時に到着しても構いません。また、ゴール地点に到着した馬車はそこで止まり、ずっとゴール地点にいます。
- "ほそながいところ"は大変細長いため馬車は基本的に同じ場所に2台並ぶことはできません。しかし、特別に"すこしひろいところ"がm箇所あり、そこでのみ2台まで並ぶことができ、ある馬車が別の馬車を追い抜くことが可能です。
また、先述した"ほそながいところ"と"すこしひろいところ"について、以下の制約を満たします。
- スタート地点からゴール地点までは直線的に結ばれており、その距離は(dist)km(distは1以上の整数)
- m箇所の"すこしひろいところ"はスタート地点からゴール地点までのどこかにあり、それらはいずれもスタート地点およびゴール地点とは重なりません。また、それぞれの"すこしひろいところ"はスタート地点からちょうど(Di)km(Diは1以上の整数)の地点にあります。
これを聞いた高橋君は、以上に述べた馬車運行のルールを守りつつ馬車の出発時刻を調整することにより、1台目の馬車が発車してからすべての馬車が到着するまでにかかる時間を小さくできることを見抜きました。 高橋君の出した結果を知るために、 馬車の台数n , それぞれの馬車の速度に関するパラメータSi,"ほそながいところ"上に存在する"すこしひろいところ"の総数m ,それぞれの"すこしひろいところ"のスタート地点からの距離Di が与えられるので、 1台目の馬車が発車してからすべての馬車が到着するまでにかかる時間の最小値を求めるプログラムを書くことがあなたの仕事です。 なお、苹果ちゃんは"ほそながいところ"での観光を存分に楽しみましたが、高橋君はこの観光の後には「ほそながかった…」としかつぶやかなかったそうです。
Input
入力形式は以下のようになっている。
dist
n
S1
S2
..
Sn
m
D1
D2
..
Dm
- distはスタート地点からゴール地点までの距離(km)を表す
- nはスタート地点を発車する馬車の数を表す
- Siは馬車の速度を表し、i番目に出発する馬車は1kmを(Si)分で進むことを表す。
- mは"すこしひろいところ"の総数を表す
- Diはスタート地点からそれぞれの"すこしひろいところ"への距離(km)を表す。
Constraints
1≤dist≤100000000(108)
1≤n≤5
0≤m≤5
1≤Si≤100
0<Di<dist
i≠jならばDi≠Dj
入力に出現する数はすべて整数である。
- i < jならば、i番目に出発する馬車はj番目の馬車より1分以上早く出発しなければならない
Output
1台目の馬車が発車してからすべての馬車が到着するまでにかかる時間の最小値を1行に出力せよ。単位は分である。
Sample Input 1
100 2 1 2 0
Output for the Sample Input 1
201
2台目は1台目が出発した1分後に出発する。
Sample Input 2
100 2 2 1 0
Output for the Sample Input 2
200
2台目は1台目が出発した100分後に出発し、ゴールで1台目に追いつく。
Sample Input 3
100 3 2 1 1 1 50
Output for the Sample Input 3
200
2台目は1台目が出発した50分後に出発し、50mのひろいところで1台目を抜く。
3台目は1台目が出発した100分後に出発し、ゴールで1台目に追いつく。
Sample Input 4
100 4 3 1 1 3 2 40 60
Output for the Sample Input 4
421