시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 751 379 304 52.144%

문제

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1

7
1
W3sicHJvYmxlbV9pZCI6Ijc3OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJhMzlcdWM3NDQgXHVhYzgzXHVjNzc4XHVhYzAwIFx1YmEzOVx1ZDc5MCBcdWFjODNcdWM3NzhcdWFjMDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJlY1x1ZDU3NFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODg1XHViOTU4XHVjNzU4IFx1YzBkZFx1YmE4NVx1Y2NiNCBBXHVjNjQwIEJcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBBXHViMjk0IEJcdWI5N2MgXHViYTM5XHViMjk0XHViMmU0LiBBXHViMjk0IFx1Yzc5MFx1YWUzMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjNzkxXHVjNzQwIFx1YmEzOVx1Yzc3NFx1YjljYyBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgezgsIDEsIDcsIDMsIDF9XHVjNzc0XHVhY2UwLCBCXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCB7MywgNiwgMX1cdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIEFcdWFjMDAgQlx1Yjk3YyBcdWJhMzlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDdcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiA4LTMsIDgtNiwgOC0xLCA3LTMsIDctNiwgNy0xLCAzLTEuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZWUoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTY0cHg7IHdpZHRoOjIwOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMwZGRcdWJhODVcdWNjYjQgQVx1YzY0MCBCXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBBXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBCXHViY2Y0XHViMmU0IFx1ZDA3MCBcdWMzMGRcdWM3NzQgXHViYTg3IFx1YWMxY1x1YjA5OCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IEFcdWM3NTggXHVjMjE4IE5cdWFjZmMgQlx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgQVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHViYWE4XHViNDUwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBCXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQwNmNcdWFlMzBcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4mbmJzcDsoMSAmbGU7IE4sIE0gJmxlOyAyMCwwMDApJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQsIEFcdWFjMDAgQlx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzc5NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVhdCBvciBCZSBFYXRlbiIsImRlc2NyaXB0aW9uIjoiPHA+RGVlcCBkb3duIHVuZGVyIHRoZSBzZWEsIHRoZXJlJnJzcXVvO3JlIHR3byBraW5kcyBvZiBsaXZpbmcgb3JnYW5pc20sIGxldCZyc3F1bztzIHNheSBBIGFuZCBCLiBBIGlzIEImcnNxdW87cyBwcmVkYXRvciwgYnV0IEEgd2lsbCBvbmx5IGVhdCBCIGlmIGFuZCBvbmx5IGlmIGl0cyBzaXplIGlzIHN0cmljdGx5IGJpZ2dlciB0aGFuIGl0cyBwcmV5LiBGb3IgZXhhbXBsZSwgbGV0IHRoZSBzaXplIG9mIEEgPSB7OCwgMSwgNywgMywgMX0gYW5kIEIgPSB7MywgNiwgMX0sIHRoZW4gdGhlcmUgYXJlIDcgcGFpcnMgb2YgQSAmbmRhc2g7IEIgd2hlcmUgQSAmZ3Q7IEI6IDggJm5kYXNoOyAzLCA4ICZuZGFzaDsgNiwgOCAmbmRhc2g7IDEsIDcgJm5kYXNoOyAzLCA3ICZuZGFzaDsgNiwgNyAmbmRhc2g7IDEsIDMgJm5kYXNoOyAxLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2VlKDEpLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2NHB4OyB3aWR0aDoyMDlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgc2l6ZSBvZiBlYWNoIG9yZ2FuaXNtIGluIEEgYW5kIEIsIHdyaXRlIGEgcHJvZ3JhbSB0byBjb3VudCBob3cgbWFueSBwYWlyIG9mIEEgLSBCIGFyZSB0aGVyZSBzdWNoIHRoYXQgQSBpcyBzdHJpY3RseSBiaWdnZXIgdGhhbiBCLiBZb3VyIHByb2dyYW0gc2hvdWxkIGJlIGVmZmljaWVudCBhcyB0aGUgbnVtYmVyIG9mIG9yZ2FuaXNtIG1heSBiZSBsYXJnZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgVCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIGZvbGxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBjYXNlIHdpbGwgYmVnaW4gd2l0aCB0d28gaW50ZWdlcnMgTiAoMSAmbGU7IE4gJmxlOyAyMCwwMDApIGFuZCBNICgxICZsZTsgTSAmbGU7IDIwLDAwMCksIGRlbm90aW5nIHRoZSBudW1iZXIgb2Ygb3JnYW5pc20gQSBhbmQgQiByZXNwZWN0aXZlbHkuIFRoZSBuZXh0IGxpbmUgd2lsbCBjb250YWluIE4gcG9zaXRpdmUgaW50ZWdlcnMgcmVwcmVzZW50IHRoZSBzaXplIG9mIGVhY2ggQSBvcmdhbmlzbS4gVGhlIHRoaXJkIGxpbmUgd2lsbCBjb250YWluIE0gcG9zaXRpdmUgaW50ZWdlcnMgcmVwcmVzZW50IHRoZSBzaXplIG9mIGVhY2ggQiBvcmdhbmlzbS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBwcmludCBvbiBhIHNpbmdsZSBsaW5lIHRoZSBudW1iZXIgb2YgcGFpciBBICZuZGFzaDsgQiBzdWNoIHRoYXQgQSBpcyBzdHJpY3RseSBsYXJnZXIgdGhhbiBCLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=