#P3434. Tube Disc Drop

    ID: 16689 Type: Default 1000ms 256MiB

Tube Disc Drop

Tube Disc Drop

Johnny received an unusual birthday gift from his parents: a tube and a set of circular discs. The tube is composed of several cylindrical segments of equal height, and each disc has the same height as one cylinder. Each cylinder has a circular hole with a diameter that may vary from segment to segment.

Johnny invented a game where he drops the discs into the tube one by one in a fixed order. A disc will continue falling until one of two things occurs:

  1. The disc cannot pass through the hole of the next tube segment (i.e. the disc's diameter is greater than the hole's diameter).
  2. The disc is stopped by a previously dropped disc occupying a segment below.

Your task is to determine the depth (1-indexed from the top) at which the last disc will come to rest. If at any point a disc cannot be placed (i.e. it falls through the tube), output 0.

Note: Let \( D_i \) be the diameter of the hole of the \( i \)-th segment from the top and \( d_j \) be the diameter of the \( j \)-th disc. The effective diameter available at a depth is the minimum of all \( D_i \) from the top down to that depth. Each disc is dropped in sequence and can only fall as deep as allowed by both the tube's holes and the discs already placed above.

inputFormat

The input begins with a line containing two integers \( N \) and \( K \) separated by a space, where \( N \) is the number of cylindrical segments in the tube and \( K \) is the number of discs.

The second line contains \( N \) space-separated integers: \( D_1, D_2, \ldots, D_N \), representing the diameters of the holes from the top to the bottom of the tube.

The third line contains \( K \) space-separated integers: \( d_1, d_2, \ldots, d_K \), representing the diameters of the discs in the order they are dropped.

outputFormat

Output a single integer representing the depth (1-indexed) at which the last disc stops. If a disc cannot be placed in the tube, output 0.

sample

7 3
5 6 4 3 6 2 3
3 2 5
2