思考题 inspired by car lanes

Car Lane

In Ryuto the capital of the Dragon Kingdom, there is an intersection with k+1 exits. On one lane of one exit, there is a queue of n cars. The i-th car in the queue wants to go in the direction d_i (1\leq d_i\leq k). There is a traffic light with m states. In state i, cars with direction l_{i,1},...,l_{i,c_i} are permitted to travel through the intersection.

A car can travel through the intersection and leave the queue iff both:

• There is no car in front of him in the queue
• The traffic light permits travelling in that direction

Now evil you are in control of the switching of the states of the traffic light. You want to control the light so that the queue gets cleared in M valid state-changes where M is as large as possible. A change is valid if after the change at least 1 car passes. You start in state 0 where no cars can travel. But there's a twist: all cars have a super-sonic upgrade and can boot up and leave the intersection immediately before you can respond. In other words, you can only switch states when ALL cars in the queue cannot travel through the intersection.

Find the M.

Constraints

1\leq n,m,k,\sum c_i\leq 10^5

Example

d={1,2,2,3,1,2}, l={{1,3},{2,3}}

Answer=4

Explanation:

• Start in state 0
• Switch to state 1, d={2,2,3,1,2} now
• Switch to state 2, d={1,2} now
• Switch to state 1, d={2} now
• Switch to state 2, d={} now

Hint

Greedy.

Also remember that \sum c_i\leq 10^5.