시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB137777.778%

문제

넥슨에서는 대학생들을 대상으로 주어진 게임 환경에서 승리할 수 있는 AI 코드를 개발해 대결하는 전략적 팀 프로그래밍 대회를 개최했다. 성황리에 진행된 작년 대회에 이어 올해도 대학생을 대상으로 진행될 예정이다! NYPC에 참가하고 싶던 달구와 윤이는, 대회 전 예행연습을 위해 직접 게임 하나를 만들어 보기로 하였다. 게임의 규칙은 다음과 같다.

  • 윤이와 달구는 각자 $1$ 이상 $K$ 이하의 정수가 적혀 있는 카드를 중복을 허용하여 무작위로 $N$장씩 가진다.
  • 게임은 총 $N$라운드 동안 진행되며, 매 라운드마다 자신이 가진 카드 중 하나를 낸다.
  • 두 사람이 낸 카드에 적힌 수의 차가 홀수라면 적힌 수가 큰 플레이어가, 짝수라면 적힌 수가 작은 플레이어가 승리한다.
  • 만약 윤이와 달구가 낸 카드에 적힌 수가 같다면, 해당 라운드는 승자 없이 무승부로 처리한다.
  • 각 라운드가 끝난 뒤 사용한 카드는 버린다.

최적으로 게임을 플레이하는 AI 코드를 개발하기 전, 달구는 자신이 승리할 수 있는 라운드 수의 최댓값을 미리 알고 싶어졌다. 윤이와 달구가 초기에 받은 카드가 주어졌을 때, 달구가 승리할 수 있는 라운드 수의 최댓값을 구해보자.

입력

첫째 줄에 각 플레이어의 카드의 장수 $N$과 카드에 적힐 수 있는 수의 최댓값 $K$가 공백으로 구분되어 주어진다. $(1\leq N, K\leq 500\,000)$

둘째 줄에 윤이가 받은 카드에 적힌 수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1\leq A_i\leq K)$

셋째 줄에 달구가 받은 카드에 적힌 수 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. $(1\leq B_i\leq K)$

출력

첫째 줄에 달구가 승리할 수 있는 라운드 수의 최댓값을 출력한다.

예제 입력 1

3 3
1 3 1
3 2 1

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjM1NDc2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmVjXHVhZDZjXHVjNjQwIFx1YzcyNFx1Yzc3NFx1Yzc1OCBcdWNlNzRcdWI0ZGMgXHViYzMwXHVkMmMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxMjVcdWMyYThcdWM1ZDBcdWMxMWNcdWIyOTQgXHViMzAwXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YjMwMFx1YzBjMVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzhjXHVjNzg0IFx1ZDY1OFx1YWNiZFx1YzVkMFx1YzExYyBcdWMyYjlcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBBSSBcdWNmNTRcdWI0ZGNcdWI5N2MgXHVhYzFjXHViYzFjXHVkNTc0IFx1YjMwMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM4MDEgXHVkMzAwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWIzMDBcdWQ2OGNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTg4XHViMmU0LiBcdWMxMzFcdWQ2NjlcdWI5YWNcdWM1ZDAgXHVjOWM0XHVkNTg5XHViNDFjIFx1Yzc5MVx1YjE0NCBcdWIzMDBcdWQ2OGNcdWM1ZDAgXHVjNzc0XHVjNWI0IFx1YzYyY1x1ZDU3NFx1YjNjNCBcdWIzMDBcdWQ1NTlcdWMwZGRcdWM3NDQgXHViMzAwXHVjMGMxXHVjNzNjXHViODVjIFx1YzljNFx1ZDU4OVx1YjQyMCBcdWM2MDhcdWM4MTVcdWM3NzRcdWIyZTQhIE5ZUENcdWM1ZDAgXHVjYzM4XHVhYzAwXHVkNTU4XHVhY2UwIFx1YzJmNlx1YjM1OCBcdWIyZWNcdWFkNmNcdWM2NDAgXHVjNzI0XHVjNzc0XHViMjk0LCBcdWIzMDBcdWQ2OGMgXHVjODA0IFx1YzYwOFx1ZDU4OVx1YzVmMFx1YzJiNVx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVjOWMxXHVjODExIFx1YWM4Y1x1Yzc4NCBcdWQ1NThcdWIwOThcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0IFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG48bGk+XHVjNzI0XHVjNzc0XHVjNjQwIFx1YjJlY1x1YWQ2Y1x1YjI5NCBcdWFjMDFcdWM3OTAgJDEkIFx1Yzc3NFx1YzBjMSAkSyQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWM5MTFcdWJjZjVcdWM3NDQgXHVkNWM4XHVjNmE5XHVkNTU4XHVjNWVjIFx1YmIzNFx1Yzc5MVx1YzcwNFx1Yjg1YyAkTiRcdWM3YTVcdWM1MjkgXHVhYzAwXHVjOWM0XHViMmU0LjxcL2xpPlxyXG48bGk+XHVhYzhjXHVjNzg0XHVjNzQwIFx1Y2QxZCAkTiRcdWI3N2NcdWM2YjRcdWI0ZGMgXHViM2Q5XHVjNTQ4IFx1YzljNFx1ZDU4OVx1YjQxOFx1YmE3MCwgXHViOWU0IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YjljOFx1YjJlNCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhYzAwXHVjOWM0IFx1Y2U3NFx1YjRkYyBcdWM5MTEgXHVkNTU4XHViMDk4XHViOTdjIFx1YjBiOFx1YjJlNC48XC9saT5cclxuPGxpPlx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NzQgXHViMGI4IFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4XHVjNzU4IFx1Y2MyOFx1YWMwMCBcdWQ2NDBcdWMyMThcdWI3N2NcdWJhNzQgXHVjODAxXHVkNzhjIFx1YzIxOFx1YWMwMCBcdWQwNzAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwLCBcdWM5ZGRcdWMyMThcdWI3N2NcdWJhNzQgXHVjODAxXHVkNzhjIFx1YzIxOFx1YWMwMCBcdWM3OTFcdWM3NDAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YzJiOVx1YjlhY1x1ZDU1Y1x1YjJlNC48XC9saT5cclxuPGxpPlx1YjljY1x1YzU3ZCBcdWM3MjRcdWM3NzRcdWM2NDAgXHViMmVjXHVhZDZjXHVhYzAwIFx1YjBiOCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzIxOFx1YWMwMCBcdWFjMTlcdWIyZTRcdWJhNzQsIFx1ZDU3NFx1YjJmOSBcdWI3N2NcdWM2YjRcdWI0ZGNcdWIyOTQgXHVjMmI5XHVjNzkwIFx1YzVjNlx1Yzc3NCBcdWJiMzRcdWMyYjlcdWJkODBcdWI4NWMgXHVjYzk4XHViOWFjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48bGk+XHVhYzAxIFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YWMwMCBcdWIwNWRcdWIwOWMgXHViNGE0IFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWNlNzRcdWI0ZGNcdWIyOTQgXHViYzg0XHViOWIwXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Y2Q1Y1x1YzgwMVx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTBjXHViODA4XHVjNzc0XHVkNTU4XHViMjk0IEFJIFx1Y2Y1NFx1YjRkY1x1Yjk3YyBcdWFjMWNcdWJjMWNcdWQ1NThcdWFlMzAgXHVjODA0LCBcdWIyZWNcdWFkNmNcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzc0IFx1YzJiOVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yjc3Y1x1YzZiNFx1YjRkYyBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YmJmOFx1YjlhYyBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LiBcdWM3MjRcdWM3NzRcdWM2NDAgXHViMmVjXHVhZDZjXHVhYzAwIFx1Y2QwOFx1YWUzMFx1YzVkMCBcdWJjMWJcdWM3NDAgXHVjZTc0XHViNGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjJlY1x1YWQ2Y1x1YWMwMCBcdWMyYjlcdWI5YWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWI3N2NcdWM2YjRcdWI0ZGMgXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM3NTggXHVjZTc0XHViNGRjXHVjNzU4IFx1YzdhNVx1YzIxOCAkTiRcdWFjZmMgXHVjZTc0XHViNGRjXHVjNWQwIFx1YzgwMVx1ZDc5MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTIgJEskXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDFcXGxlcSBOLCBLXFxsZXEgNTAwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3MjRcdWM3NzRcdWFjMDAgXHViYzFiXHVjNzQwIFx1Y2U3NFx1YjRkY1x1YzVkMCBcdWM4MDFcdWQ3OGMgXHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxXFxsZXEgQV9pXFxsZXEgSykkPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmVjXHVhZDZjXHVhYzAwIFx1YmMxYlx1Yzc0MCBcdWNlNzRcdWI0ZGNcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzIxOCAkQl8xLCBCXzIsIFxcY2RvdHMsIEJfTiRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMVxcbGVxIEJfaVxcbGVxIEspJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmVjXHVhZDZjXHVhYzAwIFx1YzJiOVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Yjc3Y1x1YzZiNFx1YjRkYyBcdWMyMThcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNTQ3NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRhbGd1IGFuZCBZdW5lZSdzIENhcmQgQmF0dGxlIiwiZGVzY3JpcHRpb24iOiI8cD5OZXhvbiByZWNlbnRseSBob3N0ZWQgYSBzdHJhdGVnaWMgdGVhbSBwcm9ncmFtbWluZyBjb21wZXRpdGlvbiB3aGVyZSB1bml2ZXJzaXR5IHN0dWRlbnRzIGRldmVsb3BlZCBBSSBjb2RlcyB0byBjb21wZXRlIGZvciB2aWN0b3J5IHdpdGhpbiBhIGdpdmVuIGdhbWUgZW52aXJvbm1lbnQuIEZvbGxvd2luZyB0aGUgaHVnZSBzdWNjZXNzIG9mIGxhc3QgeWVhciZyc3F1bztzIGV2ZW50LCB0aGUgY29tcGV0aXRpb24gaXMgc2V0IHRvIHJldHVybiBmb3IgdW5pdmVyc2l0eSBzdHVkZW50cyBhZ2FpbiB0aGlzIHllYXIhIERhbGd1IGFuZCBZdW5lZSwgd2hvIHdlcmUgZWFnZXIgdG8gcGFydGljaXBhdGUgaW4gdGhlIE5ZUEMsIGRlY2lkZWQgdG8gY3JlYXRlIGEgZ2FtZSBvZiB0aGVpciBvd24gZm9yIGEgcHJlLWNvbXBldGl0aW9uIHByYWN0aWNlIHNlc3Npb24uIFRoZSBydWxlcyBvZiB0aGUgZ2FtZSBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5ZdW5lZSBhbmQgRGFsZ3UgZWFjaCBoYXZlICROJCBjYXJkcywgZWFjaCB3aXRoIGFuIGludGVnZXIgYmV0d2VlbiAkMSQgYW5kICRLJCBpbmNsdXNpdmUsIHJhbmRvbWx5IGFzc2lnbmVkIHdpdGggZHVwbGljYXRlcyBhbGxvd2VkLjxcL2xpPlxyXG5cdDxsaT5UaGUgZ2FtZSBjb25zaXN0cyBvZiAkTiQgcm91bmRzLiBJbiBlYWNoIHJvdW5kLCBlYWNoIHBsYXllciBwbGF5cyBvbmUgb2YgdGhlaXIgY2FyZHMuPFwvbGk+XHJcblx0PGxpPklmIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIG51bWJlcnMgb24gdGhlIGNhcmRzIGlzIG9kZCwgdGhlIHBsYXllciB3aXRoIHRoZSBoaWdoZXIgbnVtYmVyIHdpbnM7IGlmIHRoZSBkaWZmZXJlbmNlIGlzIGV2ZW4sIHRoZSBwbGF5ZXIgd2l0aCB0aGUgbG93ZXIgbnVtYmVyIHdpbnMuPFwvbGk+XHJcblx0PGxpPklmIHRoZSBudW1iZXJzIG9uIHRoZSBjYXJkcyBwbGF5ZWQgYnkgWXVuZWUgYW5kIERhbGd1IGFyZSBlcXVhbCwgdGhlIHJvdW5kIGVuZHMgaW4gYSBkcmF3IHdpdGggbm8gd2lubmVyLjxcL2xpPlxyXG5cdDxsaT5BZnRlciBlYWNoIHJvdW5kLCB0aGUgcGxheWVkIGNhcmRzIGFyZSBkaXNjYXJkZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QmVmb3JlIGRldmVsb3BpbmcgdGhlIEFJIGNvZGUgdG8gcGxheSB0aGUgZ2FtZSBvcHRpbWFsbHksIERhbGd1IHdhbnRzIHRvIGRldGVybWluZSB0aGUgbWF4aW11bSBudW1iZXIgb2Ygcm91bmRzIERhbGd1IGNhbiBwb3NzaWJseSB3aW4uIEdpdmVuIHRoZSBjYXJkcyBpbml0aWFsbHkgcmVjZWl2ZWQgYnkgWXVuZWUgYW5kIERhbGd1LCBmaW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiByb3VuZHMgRGFsZ3UgY2FuIHdpbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2YgY2FyZHMgZWFjaCBwbGF5ZXIgaGFzLCAkTiQsIGFuZCB0aGUgbWF4aW11bSBwb3NzaWJsZSB2YWx1ZSBvbiBhIGNhcmQsICRLJCwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICQoMVxcbGVxIE4sS1xcbGVxIDUwMFxcLCAwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGludGVnZXJzICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJCBvbiB0aGUgY2FyZHMgcmVjZWl2ZWQgYnkgWXVuZWUsIHNlcGFyYXRlZCBieSBzcGFjZXMuICQoMVxcbGVxIEFfaVxcbGVxIEspJDxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyB0aGUgaW50ZWdlcnMgJEJfMSwgQl8yLCBcXGNkb3RzLCBCX04kIG9uIHRoZSBjYXJkcyByZWNlaXZlZCBieSBEYWxndSwgc2VwYXJhdGVkIGJ5IHNwYWNlcy4gJCgxXFxsZXEgQl9pXFxsZXEgSykkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvdW5kcyBEYWxndSBjYW4gd2luLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=