눈싸움 2

IOI 기간 동안 스웨덴과 핀란드는 서로 눈싸움을 한다. 진행 방식은 다음과 같다.

• 두 나라 중 한 나라, 이를테면 핀란드가 다른 나라를 향해 눈덩이를 하나 던진다.

• 그러면 스웨덴은 (정당방위로) 그보다 더 큰 눈덩이를 되던진다.

• 그러면 핀란드도 더 큰 눈덩이를 되던진다.

• ... 이런 식으로 어느 한 나라가 빗맞힐 때까지 계속된다(이는 첫 번째 투척부터 일어날 수도 있다).

• 그 후 모든 과정이 다시 시작되며, 더 작은 눈덩이로 시작할 수도 있고 다른 나라가 그 눈덩이를 던질 수도 있다.

눈싸움이 끝난 뒤 다른 몇몇 나라의 팀 지도자들이 현장에 찾아온다. 그들은 땅에 남은 던져진 눈덩이의 잔해를 보고 그 양에 경악한다. 이 사안은 다음 IOI 이사회 회의에서 다뤄야 한다! 누군가는 벌로 대회 기간에 스웨덴과 핀란드의 사탕을 금지하자고 제안한다. 스웨덴과 핀란드는 항변한다. 그저 정당방위였을 뿐이라고!

각 방향으로 던져진 눈덩이들의 크기가 주어질 때, 그중 최대 몇 개가 정당방위로 던져졌을 수 있는가?

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 테스트된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 | 기타

1 | 19 |$1 \le N,M \le 1000$| 스웨덴이 던진 모든 눈덩이가 빗나간다고 가정해도 된다.

2 | 23 |$1 \le N,M \le 1000$| 핀란드가 항상 첫 번째 눈덩이를 던진다고 가정해도 된다.

3 | 20 |$1 \le N,M \le 1000$| 크기가 같은 눈덩이는 없다고 가정해도 된다.

4 | 38 |$1 \le N,M \le 100\,000$|

첫째 줄에는 두 수 $N$과 $M$이 주어지며, $1 \le N,M \le 100\,000$이다. 둘째 줄에는 스웨덴이 던진 눈덩이의 크기를 나타내는 $N$개의 수 $a_i$ ($1 \le a_i \le 1\,000\,000$)가 주어진다. 셋째 줄에는 핀란드가 던진 눈덩이의 크기를 나타내는 $M$개의 수 $b_i$ ($1 \le b_i \le 1\,000\,000$)가 주어진다.

두 수열은 모두 오름차순으로 주어진다.

수 하나를 출력한다. 정당방위로 던져졌을 수 있는 눈덩이의 최대 개수이다.

첫 번째 예제에서 스웨덴은 각각 크기가 1, 3, 4, 5인 눈덩이 네 개를 던졌고, 핀란드는 크기가 2와 3인 눈덩이 두 개를 던졌다.

예를 들어 스웨덴이 핀란드를 향해 크기 1인 눈덩이를 던지며 시작하고, 핀란드가 정당방위로 크기 2인 눈덩이를 되던진 뒤, 스웨덴이 크기 3인 눈덩이로 응수했지만 빗맞히는 식으로 진행되었을 수 있다. 그 후 핀란드가 남은 크기 2인 눈덩이를 던지고, 스웨덴이 크기 4인 눈덩이로 응수했지만 다시 빗맞힌다. 스웨덴은 마지막 크기 5인 눈덩이도 빗맞힌다. 정당방위로 던져진 눈덩이는 모두 3개이다.

두 번째 예제에서는 어떤 눈덩이도 정당방위로 던져졌을 수 없다. 정당방위로 던진 눈덩이는 그보다 앞서 던진 눈덩이보다 더 커야 하기 때문이다.