Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 から N の番号がついた N 頭のラクダがいます。
ラクダ i の体重は w_i です。
あなたはラクダたちに隊列を組ませ、M 個のパーツからなる橋を渡らせようとしています。
あなたは橋を渡る前にラクダたちの隊列を決め(番号の昇順となる必要はありません)、ラクダどうしを任意の非負の実数の間隔で並ばせることができます。 ラクダたちはこの決められた間隔を保って橋を渡ります。
橋の i 番目のパーツは長さ l_i で耐荷重は v_i です。 パーツ内部(両端を除く)にいるラクダたちの体重の総和が v_i より大きくなると、橋は崩落してしまいます。
橋が崩落しないようにラクダたちを渡らせることが可能かどうかを判定し、可能ならばそのときの先頭のラクダと末尾のラクダの距離としてありうる値の最小値を求めてください。 これは整数になることが証明できるので、整数で出力してください。
制約
- 与えられる入力は全て整数
- 2 \leq N \leq 8
- 1 \leq M \leq 10^5
- 1 \leq w_i,l_i,v_i \leq 10^8
入力
入力は以下の形式で標準入力から与えられる。
N M w_1 w_2 \cdots w_N l_1 v_1 \vdots l_M v_M
出力
どのようにしても橋が崩落してしまう場合、-1
を出力せよ。
そうでない場合、橋が崩落しないようにラクダたちを渡らせるときの先頭のラクダと末尾のラクダの距離としてありうる値の最小値を出力せよ。
入力例 1
3 2 1 4 2 10 4 2 6
出力例 1
10
- 例えば、先頭から順に 1,3,2 の順番に並べ、ラクダどうしの間隔をそれぞれ 0,10 にすることで橋が崩落しないようにラクダたちを渡らせることが可能です。
- パーツ 1 ではラクダ 1,3 あるいはラクダ 2 のみがパーツの内部にいる状態が起こります。どちらもパーツの内部にいるラクダたちの体重の総和がパーツ 1 の耐荷重である 4 以下のため、橋が崩落することはありません。
- パーツ 2 ではラクダ 1,3 あるいはラクダ 2 のみがパーツの内部にいる状態が起こります。どちらもパーツの内部にいるラクダたちの体重の総和がパーツ 1 の耐荷重である 6 以下のため、橋が崩落することはありません。
- ラクダどうしの間隔が 0 でもよいこと、パーツの内部はパーツの両端を含まないことに注意してください。
入力例 2
2 1 12 345 1 1
出力例 2
-1
- どのようにしても橋が崩落してしまう場合は
-1
を出力してください。
入力例 3
8 1 1 1 1 1 1 1 1 1 100000000 1
出力例 3
700000000
入力例 4
8 20 57 806 244 349 608 849 513 857 778 993 939 864 152 984 308 975 46 860 123 956 21 950 850 876 441 899 249 949 387 918 34 965 536 900 875 889 264 886 583 919 88 954 845 869 208 963 511 975
出力例 4
3802
Score : 500 points
Problem Statement
There are N camels numbered 1 through N.
The weight of Camel i is w_i.
You will arrange the camels in a line and make them cross a bridge consisting of M parts.
Before they cross the bridge, you can choose their order in the line - it does not have to be Camel 1, 2, \ldots, N from front to back - and specify the distance between each adjacent pair of camels to be any non-negative real number. The camels will keep the specified distances between them while crossing the bridge.
The i-th part of the bridge has length l_i and weight capacity v_i. If the sum of the weights of camels inside a part (excluding the endpoints) exceeds v_i, the bridge will collapse.
Determine whether it is possible to make the camels cross the bridge without it collapsing. If it is possible, find the minimum possible distance between the first and last camels in the line in such a case.
It can be proved that the answer is always an integer, so print an integer.
Constraints
- All values in input are integers.
- 2 \leq N \leq 8
- 1 \leq M \leq 10^5
- 1 \leq w_i,l_i,v_i \leq 10^8
Input
Input is given from Standard Input in the following format:
N M w_1 w_2 \cdots w_N l_1 v_1 \vdots l_M v_M
Output
If the bridge will unavoidably collapse when the camels cross the bridge, print -1
.
Otherwise, print the minimum possible distance between the first and last camels in the line when the camels cross the bridge without it collapsing.
Sample Input 1
3 2 1 4 2 10 4 2 6
Sample Output 1
10
- It is possible to make the camels cross the bridge without it collapsing by, for example, arranging them in the order 1, 3, 2 from front to back, and setting the distances between them to be 0, 10.
- For Part 1 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 4 - the weight capacity of Part 1 - so there is no collapse.
- For Part 2 of the bridge, there are moments when only Camel 1 and 3 are inside the part and moments when only Camel 2 is inside the part. In both cases, the sum of the weights of camels does not exceed 6 - the weight capacity of Part 2 - so there is no collapse.
- Note that the distance between two camels may be 0 and that camels on endpoints of a part are not considered to be inside the part.
Sample Input 2
2 1 12 345 1 1
Sample Output 2
-1
- Print
-1
if the bridge will unavoidably collapse.
Sample Input 3
8 1 1 1 1 1 1 1 1 1 100000000 1
Sample Output 3
700000000
Sample Input 4
8 20 57 806 244 349 608 849 513 857 778 993 939 864 152 984 308 975 46 860 123 956 21 950 850 876 441 899 249 949 387 918 34 965 536 900 875 889 264 886 583 919 88 954 845 869 208 963 511 975
Sample Output 4
3802