Problem B
Scheduling events
A company MBI must rent an auditorium for organizing $K$ events $1,\dots ,K$ in a period of $N$ days $1,\dots ,N$. The event $k$ must be organized on $l_ k$ consecutive days ($\forall k = 1,\dots ,K$). Due to the pricing policy of the agent, the prices of the auditorium on different days are different: $a_ i$ is the price on day $i,\forall i=1,\dots ,N$. A schedule of each event $k$ is a sequence of $l_ k$ consecutive days on which the event happens. The event $i$ must be organized before event $j$ for all $i,j$ such that $1\leq i < j \leq K$. Find the schedules for $K$ events such that the schedules of any 2 events cannot overlap and the total price is minimal.
Input
The input file consists of following lines:
-
Line 1: $N$ and $K$ ($1\leq N\leq 10^5, 1\leq K\leq 100$),
-
Line 2: $a_1,\dots ,a_ N$ ($1\leq a_ i\leq 100,\forall i = 1,\dots ,100$),
-
Line 3: $l_1,\dots ,l_ K$ ($1\leq l_ k\leq 100,\forall k=1,\dots ,K$).
Output
Write the total minimum price (if any), or write the value -1 if there does not exist any solution.
Sample Clarification
In the sample below,
-
The schedule of event 1 is the sequence of days: 1, 2.
-
The schedule of event 2 is the sequence of days: 5, 6, 7, 8.
The total price is (2 + 3) + (5 + 7 + 1 + 1) = 19.
| Sample Input 1 | Sample Output 1 |
|---|---|
8 2 2 3 6 4 5 7 1 1 2 4 |
19 |
