교육

EduCorp는 사교육 시장에 뛰어들려고 경제 부트캠프 학원을 세웠다. 처음 예상과 달리 학원은 빠르게 커지고 있다.

너무 빠르게 커진 나머지 학생이 지금 건물에 다 들어가지 못한다. 새 건물을 짓는 동안 학생을 다른 곳에 수용해야 한다.

각 학과는 원래 쓰던 공간을 팔고 따로 빌린 건물로 옮긴다. 학과끼리 건물을 나눠 쓰지 않으므로 건물 하나에는 학과 하나만 들어간다. 경제를 가르치는 학원답게, 근처에서 빌릴 수 있는 건물의 수용 인원과 임대료는 과제로 위장한 조사로 이미 모아 두었다.

남은 일은 총 임대료가 가장 적어지도록 빌릴 건물을 고르는 것이다.

첫째 줄에 학과의 수 $n$과 건물의 수 $m$이 주어진다. ($1 \le n \le m \le 5000$)

둘째 줄에 정수 $s_1, \dots, s_n$이 주어진다. $s_i$는 $i$번 학과의 학생 수다. ($1 \le s_i \le 1000$)

셋째 줄에 정수 $p_1, \dots, p_m$이 주어진다. $p_j$는 $j$번 건물의 수용 인원이다. ($1 \le p_j \le 1000$)

넷째 줄에 정수 $r_1, \dots, r_m$이 주어진다. $r_j$는 $j$번 건물의 연간 임대료다. ($1 \le r_j \le 1000$)

한 줄에 있는 수는 공백 하나로 구분된다.

모든 학과에 건물을 하나씩 배정할 수 없으면 첫째 줄에 impossible을 출력한다.

배정할 수 있으면 정수 $v_1, \dots, v_n$을 공백으로 구분해 한 줄에 출력한다. $v_i$는 $i$번 학과가 빌리는 건물의 번호다. 서로 다른 학과는 서로 다른 건물을 빌리고, 모든 $i$에 대해 $p_{v_i} \ge s_i$가 성립해야 한다.

총 임대료 $r_{v_1} + \dots + r_{v_n}$이 최소인 배정은 여러 개일 수 있다. 그중 다음 규칙으로 만든 배정 하나만 정답으로 인정한다.

학생 수가 많은 학과부터 차례로 처리하고, 학생 수가 같으면 번호가 작은 학과를 먼저 처리한다. 어떤 학과의 차례에는 아직 아무 학과도 빌리지 않았고 수용 인원이 그 학과의 학생 수 이상인 건물 중에서 임대료가 가장 싼 건물을 빌린다. 임대료가 같은 건물이 여럿이면 번호가 가장 작은 건물을 빌린다. 어떤 학과의 차례에 빌릴 건물이 하나도 없으면 impossible을 출력한다.

이 규칙은 언제나 총 임대료가 최소인 배정을 만든다.