{"problem":{"name":"Camels and Bridge","description":{"content":"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 bridg","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc105_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ camels numbered $1$ through $N$.\nThe weight of Camel $i$ is $w_i$.\nYou will arrange the camels in a line and make them cross a bridge consisting of $M$ parts.\nBefore 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.\nThe $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.\nDetermine 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.\nIt can be proved that the answer is always an integer, so print an integer.\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 \\leq N \\leq 8$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq w_i,l_i,v_i \\leq 10^8$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$w_1$ $w_2$ $\\cdots$ $w_N$\n$l_1$ $v_1$\n$\\vdots$\n$l_M$ $v_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc105_c","tags":[],"sample_group":[["3 2\n1 4 2\n10 4\n2 6","10\n\n*   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$.\n    *   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.\n    *   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.\n*   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."],["2 1\n12 345\n1 1","\\-1\n\n*   Print `-1` if the bridge will unavoidably collapse."],["8 1\n1 1 1 1 1 1 1 1\n100000000 1","700000000"],["8 20\n57 806 244 349 608 849 513 857\n778 993\n939 864\n152 984\n308 975\n46 860\n123 956\n21 950\n850 876\n441 899\n249 949\n387 918\n34 965\n536 900\n875 889\n264 886\n583 919\n88 954\n845 869\n208 963\n511 975","3802"]],"created_at":"2026-03-03 11:01:14"}}