cfduels (EJOI contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, greedy, sorting, binary search

![](_page_0_Picture_0.jpeg)

# CF Duels

Two football teams, each consisting of exactly *N* players, from Chisinau, the capital of Moldova, hold a set of duels (Chisinau Football Duels). To make it interesting, they organize the football match-ups in the following 1 vs 1 format:

- There will be a total of *N* duels, each held in a different stadium.
- Each duel will have exactly one player from each of the two teams.
- Each player will take part in exactly one duel.
- Each stadium will provide a certain amount of prize money for the winner of the respective duel.
- The player with the higher skill level wins the duel. It is guaranteed that there is always a player with a higher skill level.

The champion is the team that has obtained a strictly greater amount of prize money than the opponent team after all the matches. In case of an equal obtained prize money, there is no champion.

You are the manager of the first football team, and your job is to strategically assign your *N* players to the *N* duels.

As the manager of the first football team, you have the following information:

- *N* integers, representing the skill levels of your team's players
- *N* integers, representing the skill levels of the opposing team's players

As the manager, you also sent a scout to visit each stadium. The scout visits the stadiums in increasing order from 1 to *N*, meaning he will visit stadium 1 first, then stadium 2, and will end at stadium *N*. After the scout visits stadium *i*, he will give you information regarding the skill level of the opposing team's duelist at stadium *i*.

Possibly, after the scout visits some stadiums, you can already foresee your team emerging as a champion. In other words, there is a possibility that, after your scout visits some stadiums, you will be certain that you can become the champion. **You may still need to wait for the scout to visit the rest of the stadiums in order to be able to build an assignment for your team.**

Your task is to find out the minimal number of stadiums the scout has to visit for you to be certain about that your team securing the championship, or figure out that it's impossible to become the champion.

### Input

The first line of input will contain the integer *N* (1 ≤ *N* ≤ 5 ⋅ 10<sup>4</sup>), denoting the number of duels, players per team and stadiums.

The second line will contain *N* integers *p*<sub>1</sub>, *p*<sub>2</sub>, …, *p*<sub>N</sub> (1 ≤ *p*<sub>i</sub> ≤ 10<sup>6</sup>), representing the prize money offered by stadiums 1, 2, …, *N*, respectively.

The third line contains *N* integers *b*<sub>1</sub>, *b*<sub>2</sub>, …, *b*<sub>N</sub> (1 ≤ *b*<sub>i</sub> ≤ 10<sup>6</sup>), *b*<sub>i</sub> representing the skill level reported by the scout of the opponent player in stadium *i*. (Note that this information already contains the skill levels of each of the players in the opponent team, so they are not given once again to remove redundancy).

The fourth line contains *N* integers *a*<sub>1</sub>, *a*<sub>2</sub>, …, *a*<sub>N</sub> (1 ≤ *a*<sub>i</sub> ≤ 10<sup>6</sup>), representing the skill levels of the players in your team.

#### Output

Output a single integer - the minimum number of stadiums you need information about to be certain your team can be the champion.

Additionally, you should output 0 in case you immediately know your team will be the champion in any case, or -1 if you can not find a winning strategy even after you have information of all the *N* stadiums.

## Examples

| Input                                   | Output |
|-----------------------------------------|--------|
| 5                                       |        |
| 1 5 4 3 1                               |        |
| 5 9 3 12 8                              | 3      |
| 1 10 4 2 6                              |        |
| 6                                       |        |
| 6 1 21 22 23 24                         |        |
| 1 12 6 8 10 11                          | 2      |
| 2 3 4 5 7 9                             |        |
| 3                                       |        |
| 1 1 3                                   |        |
| 3 4 6                                   | 0      |
| 2 1 7                                   |        |
| 3                                       |        |
| 1 1 3                                   |        |
| 3 4 6                                   | -1     |
| 2 1 5                                   |        |

For the first test case, after the scout shares information of stadiums 1 and 2, you are not guaranteed to be the champion. The reason is, in case the opponent assigns the players in the following way:

| Stadium                       | 1 | 2 | 3 | 4  | 5 |
|-------------------------------|---|---|---|----|---|
| Prize money                   | 1 | 5 | 4 | 3  | 1 |
| Opponent's player skill level | 5 | 9 | 8 | 12 | 3 |

Your best option is to achieve a draw:

| Stadium                   | 1 | 2  | 3 | 4 | 5 |
|---------------------------|---|----|---|---|---|
| Your player's skill level | 6 | 10 | 1 | 2 | 4 |

You will win the matches in the stadiums 1, 2 and 5, obtaining a prize money sum of 1 + 5 + 1 = 7, and your opponent will win matches in stadiums 3 and 4, obtaining a sum of 4 + 3 = 7 as well.

After the scout shares information of stadiums 1, 2 and 3, you can be certain you will be the champion. The reason is, in case the opponent assigns the players in the following way:

| Stadium                       | 1 | 2 | 3 | 4       | 5       |
|-------------------------------|---|---|---|---------|---------|
| Prize money                   | 1 | 5 | 4 | 3       | 1       |
| Opponent's player skill level | 5 | 9 | 3 | unknown | unknown |

The two options of the opponent are:

|                         |   |    |   |    |   |
|-------------------------|---|----|---|----|---|
| Option 1                |   |    |   |    |   |
| Stadium                 | 1 | 2  | 3 | 4  | 5 |
| Prize money             | 1 | 5  | 4 | 3  | 1 |
| Opponent's player skill | 5 | 9  | 3 | 12 | 8 |
| Your player's skill     | 6 | 10 | 4 | 1  | 2 |

|                         |   |    |   |   |    |
|-------------------------|---|----|---|---|----|
| Option 2                |   |    |   |   |    |
| Stadium                 | 1 | 2  | 3 | 4 | 5  |
| Prize money             | 1 | 5  | 4 | 3 | 1  |
| Opponent's player skill | 5 | 9  | 3 | 8 | 12 |
| Your player's skill     | 6 | 10 | 4 | 1 | 2  |

We can notice that in both cases our team will win matches in stadiums 1, 2 and 3, obtaining a total sum of prize money equal to 1 + 5 + 4 = 10, and the opponent will obtain a total sum of prize money equal to 3 + 1 = 4. And, since 10 > 4, we can be certain we win in both these cases so the minimum answer is 3.

For the second sample, it can be proven that after the scout provides information for stadiums 1 and 2 you will, for the first time, be certain to become the champion. However, unlike in the first sample, you won't have a fixed winning assignment. Instead, for the opponent's varying assignments in stadiums 3, 4, 5, 6 you need to have a different response strategy to win the championship.

#### Constraints and Scoring

- 1 ≤ *N* ≤ 5 ⋅ 10<sup>4</sup>.
- 1 ≤ *a*<sub>i</sub>, *b*<sub>i</sub>, *p*<sub>i</sub> ≤ 10<sup>6</sup> for all (1 ≤ *i* ≤ *N*).
- Additionally, the skill levels of all the players are distinct. In other words for any (*i*, *j*) *a*<sub>i</sub> ≠ *b*<sub>j</sub>. And for any (*i*, *j*) (*i* ≠ *j*) *a*<sub>i</sub> ≠ *a*<sub>j</sub> and *b*<sub>i</sub> ≠ *b*<sub>j</sub>.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

| Group | Score | Limits                              |
|-------|-------|-------------------------------------|
| 1     | 12    | $p_i = 1$ for all i, and $N \le 10$ |
| 2     | 16    | $p_i = 1$ for all i                 |
| 3     | 14    | The answer is either 0 or 1         |
| 4     | 18    | The answer is either -1 or $N - 1$  |
| 5     | 10    | $N \le 5$                           |
| 6     | 30    | No additional constraints           |

Starter code:

Grader code:

Setup script:

Evaluation script: