Problem D
Determining Duos
As a coach of $2n$ students, you are making $n$ duos (teams of two) for the upcoming programming contest season. After the duos have been created, they will participate in $r$ contests, each about a different topic: DP, graphs, geometry, etc. You already ran a set of internal selection contests to rank the students, and from this you were able to rank all the students with a unique integer score between $1$ and $2n$ inclusive for each topic, with $2n$ being the best.
When a duo participates in a contest on a given topic, their score will be the maximum of the two scores of the two students for this topic.
You think it would be amazing if summed up over all duos and contests, your students could achieve a total score of at least $\frac12 rn(3n+1)$. Is this possible?
Input
The input consists of:
-
One line with two integers $n$ and $r$ ($1 \leq n \leq 4000$, $1 \leq r \leq 100$), the number of duos and the number of topics.
-
$r$ lines, the $i$th of which contains $2n$ integers $x_{i,1}, \ldots , x_{i,2n}$ ($1 \leq x_{i,j} \leq 2n$ for each $i, j$) where $x_{i,j}$ is the score of student $j$ on topic $i$.
Output
If it is possible to make duos such that the total score over all duos and contests is at least $\frac12 rn(3n+1)$, output “possible”. Otherwise, output “impossible”.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 1 2 3 4 1 2 3 4 |
possible |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 2 1 2 3 4 4 1 2 3 |
possible |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 3 1 2 3 4 4 1 2 3 1 3 2 4 |
impossible |
