762. The Second Every Counter Is Cleared
n counters are numbered from 1; counter i starts at nums[i]. A schedule of m seconds
is fixed in advance: at second s the board OFFERS counter c[s].
In each second you do exactly one of:
· lower any one counter by 1, if it is above zero
· mark the offered counter c[s], but ONLY if it is already at zero
· nothing
A counter stays marked once marked. Print the earliest second by which every counter is marked,
or -1 if the schedule never allows it.
nums 2 2 0, schedule 2 2 2 2 3 2 2 1 -> 8
nums 1 3, schedule 1 1 1 2 1 1 1 -> 6
nums 0 1, schedule 2 2 2 -> -1
nums 0 0, schedule 1 2 1 2 1 2 -> 2
Trace the first example. Counter 1 is offered only at second 8, counter 2 at seconds 1, 2, 3, 4, 6 and 7, and counter 3 only at second 5, so the last chance to mark each of them is second 8, second 7 and second 5 respectively. Seconds 1 and 2 lower counter 1 to zero, seconds 3 and 4 lower counter 2 to zero, second 5 marks counter 3, which started at zero, second 6 is spare, second 7 marks counter 2 and second 8 marks counter 1. Nothing can finish sooner, because counter 1 is never offered before second 8.
## Why the answer can be searched for
Any plan that finishes by second T also finishes by second T + 1: do the same things and
idle at the end. So the seconds at which the job is possible form a suffix of 1 .. m, and the
earliest one can be found by binary search. That is the monotonicity, and it is worth stating
plainly, because the CHECK below looks as if it depends on T in a complicated way.
If second m itself is not enough, nothing is, so testing the top of the range once decides the
-1 case.
## Testing one deadline
Fix T. Two greedy choices make the test exact.
First, mark each counter at its LAST offer inside 1 .. T. Offers are the only chance to mark,
and marking late gives the earlier seconds to the lowering work; nothing is lost, because the
mark itself takes one second wherever it happens. If some counter is never offered within T,
the deadline fails immediately.
Second, walk the seconds from 1 to T carrying a count of seconds not yet spoken for. A second
that is nobody's last offer adds one to that pool. A second that IS the last offer of counter
i must pay nums[i] out of the pool for the lowering, and then spend itself on the mark:
free = 0
for s in 1 .. T:
if s is the last offer of counter i:
if free >= nums[i]: free -= nums[i]
else: this deadline is impossible
else:
free += 1
Spending from the pool is safe because every free second before s is interchangeable: lowering
counter i can be done in any of them.
## The bounds
lo = 1, hi = m. The answer is a second in the schedule or it does not exist.
## The boundary that breaks a careless implementation
A counter that starts at zero still needs a second to be marked in. nums 0 0 with schedule
1 2 1 2 1 2 answers 2, not 0. The walk handles it for free, because the marking second is
consumed rather than added to the pool, but a version that only checks "do I have enough free
seconds for the total" answers 0 and is wrong.
The second trap is recomputing the last offers for every candidate T. They change with T,
so they cannot be computed once outside the search, and a check that reuses a stale table quietly
tests the wrong instance.
## Overflow
nums[i] reaches 10^9 while the pool of free seconds never exceeds m, which is 2000. The
comparison is therefore between a huge number and a small one, and the subtraction happens only
when it is safe. Nothing here overflows, but the comparison must be written so it cannot be
skipped, because the failure is silent.
## Cost
Time O((n + m) log m). Space O(n + m).
Constraints - `1 ≤ n ≤ 2000` - `1 ≤ m ≤ 2000` - `0 ≤ nums[i] ≤ 10^9` - `1 ≤ c[s] ≤ n`
Input
The first line contains two integers n and m.
The second line contains n integers nums[1] ... nums[n], the starting values of the counters.
The third line contains m integers c[1] ... c[m], the counter offered in each second.
Output
Print one integer, the earliest second by which every counter is marked, or -1 if no second works. Print it alone on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.