시공스톤

시공스톤은 두 사람이 하는 카드 게임이다.

각 플레이어는 카드를 N장씩 받는다. 카드마다 힘과 지능 수치가 하나씩 적혀 있다. 게임이 시작되면 두 플레이어는 라운드마다 카드를 한 장씩 내려놓는다. 힘과 지능의 합이 큰 카드를 낸 쪽이 1점을 얻고, 내려놓은 카드 두 장은 모두 버린다. 이렇게 N라운드를 치른 뒤 점수가 많은 쪽이 이긴다.

택희는 이 게임을 12000시간 하고 나서 질려버렸고, 규칙을 하나 더했다. 두 플레이어는 카드 N장에 더해 조커 카드를 한 장씩 들고 시작한다. 조커는 힘 조커와 지능 조커 두 종류다. 두 플레이어는 게임을 시작하기 전에 자신의 조커를 발동할 라운드를 상대가 모르게 정한다. 조커를 사용하지 않을 수는 없다.

조커가 발동하는 라운드가 시작하는 순간부터, 게임이 끝나거나 다른 조커가 발동하기 전까지 승패를 가리는 방식이 이렇게 바뀐다.

• 힘 조커의 영향을 받는 라운드에서는 힘과 지능의 합이 아니라 힘만 비교해서 큰 쪽이 1점을 얻는다.
• 지능 조커의 영향을 받는 라운드에서는 지능만 비교해서 큰 쪽이 1점을 얻는다.

두 플레이어가 같은 라운드를 고르면 그 라운드부터는 지능 조커의 영향만 받는다.

택희는 조커가 균형에 주는 영향이 궁금해서, 역시 12000시간을 플레이한 남규와 모의 대전을 하기로 했다. 택희는 힘 조커를, 남규는 지능 조커를 들고 시작한다.

N이 6인 판이 아래처럼 흘러갔다고 하자. (a, b)는 힘이 a, 지능이 b인 카드다.

남규는 2라운드부터 지능 조커를, 택희는 5라운드부터 힘 조커를 쓰기로 정했다. 1라운드는 조커의 영향이 없어서 힘과 지능의 합이 큰 카드를 낸 택희가 1점을 얻는다. 2라운드부터 4라운드까지는 지능이 큰 쪽이 점수를 얻으므로 택희가 1점, 남규가 2점을 얻는다. 5라운드와 6라운드는 힘이 큰 카드를 낸 택희가 2점을 얻는다. 최종 점수는 택희 4점, 남규 2점이다. 이 표는 점수를 매기는 방식만 보여준다. 택희에게 가장 좋은 선택은 아니다.

모의 대전이어도 게임은 게임이다. 남규에게 지기 싫었던 택희는 남규가 카드를 낼 순서를 미리 알아냈다. 남규가 지능 조커를 몇 라운드에 쓸지는 모르지만, 택희는 단순한 전략을 세웠다. 남규가 자신에게 가장 불리한 라운드를 골랐다고 보고, 그때 남규가 얻는 점수를 최소로 만드는 것이다.

남규가 N라운드 동안 낼 카드가 순서대로 주어지고, 택희가 가진 카드 N장이 주어진다. 택희가 힘 조커를 발동할 라운드와 카드를 낼 순서를 정해서, 남규에게 가장 불리하게(택희에게 가장 유리하게) 판이 흘러갔을 때 남규가 얻는 점수를 최소로 만들어라.

첫째 줄에 카드의 수 N이 주어진다. (1 ≤ N ≤ 50)

다음 N개 줄 중 i번째 줄에 남규가 i라운드에 낼 카드의 힘 P와 지능 W가 주어진다. (1 ≤ P, W ≤ 10^9)

이어지는 N개 줄에 택희가 가진 카드의 힘 P와 지능 W가 주어진다. (1 ≤ P, W ≤ 10^9)

남규의 카드 A와 택희의 카드 B를 어떻게 고르더라도 힘, 지능, 힘과 지능의 합이 모두 서로 다르다. 즉 무승부는 없다.

첫째 줄에 택희가 힘 조커를 발동할 라운드 번호를 출력한다. 이 번호는 1 이상 N 이하다.

둘째 줄에 택희가 카드를 낼 순서를 N개의 정수로, 공백을 두고 출력한다. 카드 번호는 입력에 주어진 순서대로 1번부터 N번까지다.

조건을 만족하는 답이 여러 가지면 사전순으로 가장 작은 출력을 고른다. 먼저 첫째 줄의 라운드 번호가 가장 작은 답을 고르고, 그런 답이 여럿이면 둘째 줄의 수열이 사전순으로 가장 앞서는 답을 고른다.