15672번 - 시공스톤 스페셜 저지

시공스톤은 간단한 카드 게임으로, 남녀노소 누구나 즐길 수 있다.

이 게임의 플레이어는 두 명이며, 각 플레이어는 N 장씩의 카드를 받는다. 각 카드에는 '힘'과 '지능' 스탯이 있다. 게임이 시작되면, 각 플레이어는 라운드마다 한 장의 카드를 내려놓는다. 이때, 힘과 지능의 합이 높은 플레이어는 점수를 1점 얻게 되며, 내려놓은 두 카드는 모두 폐기한다. 이와 같이 N 라운드를 진행한 뒤, 점수가 높은 플레이어가 승리한다.

택희는 이 게임을 12000시간 동안 한 결과 게임에 질리고 말았고, 새로운 규칙을 게임에 추가하기로 했다. 각 플레이어는 N 장의 카드에 더해, 1장의 조커 카드를 더 갖고 시작한다. 조커 카드는 두 종류로, 첫 번째는 '힘 조커', 두 번째는 '지능 조커'이다. 두 플레이어는 게임 시작 전에 자신이 가진 조커의 능력을 사용할 라운드를 서로가 모르도록 정한다. 이때, 조커를 사용하지 않을 수는 없다.

각 조커가 발동할 라운드가 시작하는 순간부터는 게임이 끝나거나 다른 조커 카드의 힘이 발휘되기 전까지 각 라운드의 승패를 정하는 방식이 아래와 같이 변경된다.

• '힘 조커' 의 영향을 받는 라운드에서는 힘+지능이 아닌, 오직 힘만을 비교하여 높은 쪽이 점수를 1점 얻는다.
• 반대로 '지능 조커'의 영향을 받는 라운드에서는 지능만을 비교하여 높은 쪽이 점수를 1점 얻는다.

만일 두 플레이어가 같은 라운드에 조커를 사용하기로 한다면, '지능 조커'의 영향만을 받게 된다.

택희는 이러한 조커가 밸런스에 영향을 미치는 영향이 궁금하여, 역시 12000시간의 플레이타임을 가진 남규와 모의 대전을 해보기로 하였다.

택희는 항상 '힘 조커'를, 남규는 '지능 조커' 를 갖고 시작한다.

게임의 진행 예시는 아래와 같다.

남규는 2라운드부터 지능 조커의 힘을 사용하기로 결정하고, 택희는 5라운드부터 힘 조커를 사용하기로 결정한 상태이다.

1라운드에는 조커의 영향력이 없으므로 힘과 지능 수치의 합이 높은 카드를 낸 택희가 1점을 얻으며, 2~4라운드에는 지능의 수치가 높은 카드를 낸 쪽이 점수를 얻으므로 택희가 1점, 남규가 2점의 점수를 얻고, 5~6라운드에는 두 번 모두 힘의 수치가 더 높은 카드를 낸 택희가 2점을 얻는다.

모의 대전이어도 게임은 게임인 법. 남규에게 지기 싫었던 택희는 남규가 어떤 순서로 카드를 낼 지 미리 알아내버렸다. 하지만 남규가 지능 조커를 몇 라운드에 사용할지는 모르는 상황에서, 택희는 단순한 전략을 사용하기로 하였다. 최선의 경우에 남규가 얻을 점수가 최소가 되도록 카드의 순서와 힘 조커를 낼 타이밍을 정하기로 한 것이다.

남규가 N라운드간 낼 카드의 힘, 지능 수치가 순서대로 주어지고, 택희가 가진 N장의 카드의 능력치들이 주어진다. 택희가 힘 조커를 제시할 라운드와 택희가 카드를 낼 순서를 잘 정해,

남규에게 최악의(택희에게 이상적인) 게임이 펼쳐졌을 때 남규가 얻을 점수가 최소가 되도록 해 보자.

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

이어 N줄에 걸쳐, i번째 줄에 남규가 i라운드에 낼 카드의 힘 수치 P와 지능 수치 W가 주어진다. (1 ≤ P, W ≤ 10⁹)

이어 N줄에 걸쳐, 택희가 갖고 있는 카드의 힘 수치 P와 지능 수치 W가 주어진다. (1 ≤ P, W ≤ 10⁹)

남규가 갖고 있는 카드 A와 택희가 갖고 있는 카드 B에 대해, A, B 두 카드의 힘 수치, 지능 수치, 힘+지능의 값은 서로 다르다. 즉, 어떤 경우에도 무승부는 없다.

첫째 줄에 택희가 힘 조커의 힘을 몇 라운드부터 사용해야하는지 출력한다.

이어 둘째 줄에 N개의 정수로 택희가 낼 카드의 순서를 공백으로 구분하여 출력한다. 카드의 번호는 입력 순서대로 1부터 N까지이다.

만일 문제의 조건을 만족하는 방법이 여러 가지 있다면, 임의의 한 가지 방법만 출력한다.