Determining Duos

시간 제한3초메모리 제한1024 MB

요약

2n명 학생의 r개 주제별 순위가 주어질 때, 두 명씩 n개 듀오를 만들어 각 주제에서 두 사람 점수의 최댓값을 합한 총점이 rn(3n+1)/2 이상이 되도록 할 수 있는지 판정한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 조합론
정답자: 아직 제출이 없습니다

문제

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 $\frac 12 rn(3n+1)$ . Is this possible?

입력

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$.

출력

If it is possible to make duos such that the total score over all duos and contests is at least $\frac 12 rn(3n+1)$ , output "possible". Otherwise, output "impossible".

예제3

예제 1
입력
```
2 2
1 2 3 4
1 2 3 4
```
예상 출력
```
possible
```
예제 2
입력
```
2 2
1 2 3 4
4 1 2 3
```
예상 출력
```
possible
```
예제 3
입력
```
2 3
1 2 3 4
4 1 2 3
1 3 2 4
```
예상 출력
```
impossible
```