## An Animal Contest 3 P4 - Monkey Mayhem

View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

William the monkey finds himself in a bar! Immediately upon entering the bar William notices that something isn't right. All the monkeys in the bar are under a spell! William decides to split the bar into a grid of rows and columns — the rows are numbered through and the columns are numbered through . In this bar, William counts monkeys. There are monkeys located at the beginning of the rows, with each row from to containing one monkey at cell . Similarly, there are monkeys located at the top of the columns, with each column from to containing one monkey at cell .

So far the monkeys haven't moved, but they will soon! Since William can read minds, he knows exactly when each monkey will start moving forward. It's also possible that a monkey is so spellbound that it won't move at all! After a monkey starts moving, it continues moving at exactly one cell per second, only stopping when it leaves the grid. The monkeys at the beginning of the rows move horizontally to the right and the monkeys at the top of the columns move vertically downwards.

Given William's information, he wants to know the number of collisions that will occur between any two monkeys because he is a sadistic monkey and enjoys watching monkeys crash into each other. Note that a collision is when two monkeys arrive at the same cell at the same time. After a collision occurs, both monkeys are awakened from the spell and go home, meaning they can no longer be part of any further collisions.

If a monkey starts at the topmost row and starts moving at time , it will arrive at row at time . Similarly, if a monkey starts at the leftmost column and starts moving at time , it will arrive at column at time .

#### Input Specification

The first line contains and .

The next line contains space-separated integers , with the integer representing the time at which the monkey on the row starts moving. If is -1, the monkey will not move.

The next and final line contains space-separated integers , with the integer representing the time at which the monkey on the column starts moving. If is -1, the monkey will not move.

#### Output Specification

Output one integer representing the total number of collisions that will occur.

#### Sample Input 1

1 2
0
0 1

#### Sample Output 1

1

#### Explanation for Sample 1

For the purposes of this explanation, assume that in the above diagrams, cell is the top-leftmost cell and cell is the bottom-rightmost cell. and represent the monkeys starting on the top row and represents the monkey starting at the leftmost column.

The initial configuration at time and direction of movement for each monkey is shown by the leftmost diagram, with each subsequent diagram representing the configuration at times , , and .

At time monkeys and , having departed at time , both arrive at cell and crash into each other. They both leave the bar immediately. Monkey departs.

At time monkey arrives at cell and does not crash into monkey — monkey was already taken out by monkey earlier.

At time monkey exits the bar and our simulation is complete. We can see that collision occurred.

#### Sample Input 2

6 9
7 27 0 4 20 -1
-1 -1 9 -1 22 31 1 0 24

#### Sample Output 2

3