Problem F
Bolir
Languages
en
is
One of the most fun parts of competing in a programming contest is of course getting a shirt. But this year the planning committee has messed everything up…When a contestant registers for the contest they register their shirt size as well. But this data got lost so the committee instead ordered shirts in all kinds of sizes, hoping that the contestants could get a size they were happy with, even though it might not be the size they chose.
Now the day of the contest has arrived, and both the contestants and the shirts have arrived. There are equally many contestants and shirts, that is to say $N$ of them. The shirt sizes are denoted with integers from $1$ to $K$, and the bigger the number the bigger the shirt. The contestants are asked what shirt sizes they’d be happy with and contestant $i$ answers with a range of sizes from $L_i$ to $R_i$, where $L_i$ is the smallest size they would be happy with and $R_i$ is the largest size they would be happy with.
You are also given a list of the sizes of the shirts that the committee ordered. Can you check if the shirts can be handed out such that every contestant gets a shirt they’re happy with?
Input
On the first line there is an integer $N$ denoting both the number of contestants and the number of shirts. Then there are $N$ lines, one for each contestant. On the $i$-th of these lines there will be two integers $L_i$ and $R_i$ where $1 \leq L_i \leq R_i \leq K$, which denote the range of sizes that contestant $i$ would be happy with. Finally there is a single line with $N$ integers in the range $1$ to $K$, where each value denotes the size of a shirt.
Output
One line containing Jebb if the shirts can be assigned such that everyone is happy, or Neibb otherwise.
Explanation of Sample Inputs
In the first input there are $N = 4$ contestants and shirts. The contestants want shirts of the following sizes:
-
size between $1$ and $3$,
-
size between $1$ and $10$,
-
size between $2$ and $2$, and
-
size between $2$ and $3$.
The shirts are of sizes $1$, $2$, $2$ and $9$. If contestant $1$ gets a shirt of size $1$, contestant $2$ gets a shirt of size $9$ and contestants $3$ and $4$ each get a shirt of size $2$, then all contestants get sizes they are happy with, so the answer is Jebb.
In the second sample there are three contestants who only want a shirt of size $2$, but there are only two shirts of size $2$. Thus not everyone can get a shirt they’re happy with, so the answer is Neibb.
Scoring
The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.
Group |
Points |
Constraints |
1 |
15 |
$N \leq 10, K \leq 1\, 000$ |
2 |
15 |
$N \leq 100, K \leq 100$ |
3 |
20 |
$N \leq 1\, 000, K \leq 1\, 000$ |
4 |
20 |
$N \leq 10^5, K \leq 2$ |
5 |
15 |
$N \leq 10^5, K \leq 10^5$ |
6 |
15 |
$N \leq 10^5, K \leq 10^9$ |
Sample Input 1 | Sample Output 1 |
---|---|
4 1 3 1 10 2 2 2 3 1 2 2 9 |
Jebb |
Sample Input 2 | Sample Output 2 |
---|---|
5 1 1 1 2 2 2 2 2 2 2 1 1 1 2 2 |
Neibb |