시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 186 60 46 36.220%

문제

승혁이는 크로스워드 퍼즐을 풀고 있었다. 승혁이는 크로스워드의 개고수다. 그런데 퍼즐을 다 풀고 단어를 적어 넣으려니 서로 위치가 겹치면서 글자가 다른, 즉 틀린 경우가 발생하고 말았다. 승혁이는 답을 고치는 것 대신에 지금 알아낸 답들이 서로 충돌하지 않게 하면서 최대한 많이 배치하는 걸 하려고 한다.

현재 승혁이가 답이라 생각하는 단어들을 정해진 위치에 배치하면서, 서로 충돌하는 경우가 하나도 없게 하면서 배치할 수 있는 단어 개수는 최대 몇 개일까?

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

  • 첫째 줄에 각각 가로 단어, 세로 단어 개수를 의미하는 두 정수 H, V가 주어진다. (1 ≤ H, V ≤ 500)
  • 이어서 H개 줄에 각 가로 단어의 시작 위치 x, y, 그리고 승혁이가 답이라고 생각하는 단어 W가 주어진다. (0 ≤ x, y ≤ 1,000 이고 1 ≤ Length(W) ≤ 1,000)
  • 이어서 V개 줄에 각 세로 단어의 시작 위치 x, y, 그리고 승혁이가 답이라고 생각하는 단어 W가 주어진다. (0 ≤ x, y ≤ 1,000 이고 1 ≤ Length(W) ≤ 1,000)

모든 단어는 알파벳 대문자로만 이루어져 있으며, 가로 단어끼리 위치가 겹치거나 세로 단어끼리 위치가 겹치는 경우는 없다.

퍼즐판의 제일 왼쪽 위 칸은 x = y = 0이다. x는 가로 위치, y는 세로 위치를 결정한다. 또한 가로 단어는 오른쪽 방향으로, 세로 단어는 아래 방향으로 써내려져 간다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 출력한다.

예제 입력 1

2
2 2
0 1 BAPC
0 2 LEIDEN
0 0 SOLUTION
2 1 WINNER
1 4
0 1 HELLO
1 0 HI
2 0 BYE
3 0 GOODBYE
4 0 FAREWELL

예제 출력 1

3
4
W3sicHJvYmxlbV9pZCI6IjUzOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQyYzBcdWI4MzhcdWMyYjVcdWIyYzhcdWIyZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJiOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNmNcdWI4NWNcdWMyYTRcdWM2Y2NcdWI0ZGMgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ4MFx1YWNlMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YzJiOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNmNcdWI4NWNcdWMyYTRcdWM2Y2NcdWI0ZGNcdWM3NTggXHVhYzFjXHVhY2UwXHVjMjE4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1YjJlNCBcdWQ0ODBcdWFjZTAgXHViMmU4XHVjNWI0XHViOTdjIFx1YzgwMVx1YzViNCBcdWIxMjNcdWM3M2NcdWI4MjRcdWIyYzggXHVjMTFjXHViODVjIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFjYjlcdWNlNThcdWJhNzRcdWMxMWMgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YjJlNFx1Yjk3OCwgXHVjOTg5IFx1ZDJjMFx1YjliMCBcdWFjYmRcdWM2YjBcdWFjMDAgXHViYzFjXHVjMGRkXHVkNTU4XHVhY2UwIFx1YjlkMFx1YzU1OFx1YjJlNC4gXHVjMmI5XHVkNjAxXHVjNzc0XHViMjk0IFx1YjJmNVx1Yzc0NCBcdWFjZTBcdWNlNThcdWIyOTQgXHVhYzgzIFx1YjMwMFx1YzJlMFx1YzVkMCBcdWM5YzBcdWFlMDggXHVjNTRjXHVjNTQ0XHViMGI4IFx1YjJmNVx1YjRlNFx1Yzc3NCBcdWMxMWNcdWI4NWMgXHVjZGE5XHViM2NjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YWM4YyBcdWQ1NThcdWJhNzRcdWMxMWMgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjljZVx1Yzc3NCBcdWJjMzBcdWNlNThcdWQ1NThcdWIyOTQgXHVhYzc4IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYwNFx1YzdhYyBcdWMyYjlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViMmY1XHVjNzc0XHViNzdjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjRcdWI0ZTRcdWM3NDQgXHVjODE1XHVkNTc0XHVjOWM0IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWJjMzBcdWNlNThcdWQ1NThcdWJhNzRcdWMxMWMsIFx1YzExY1x1Yjg1YyBcdWNkYTlcdWIzY2NcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWM1YzZcdWFjOGMgXHVkNTU4XHViYTc0XHVjMTFjIFx1YmMzMFx1Y2U1OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWNcdWM3N2NcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAxXHVhYzAxIFx1YWMwMFx1Yjg1YyBcdWIyZThcdWM1YjQsIFx1YzEzOFx1Yjg1YyBcdWIyZThcdWM1YjQgXHVhYzFjXHVjMjE4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4IEgsIFZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEgsIFYgJmxlOyA1MDApPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1YzViNFx1YzExYyBIXHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVhYzAwXHViODVjIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IHgsIHksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMyYjlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViMmY1XHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjQgV1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgeCwgeSAmbGU7IDEsMDAwIFx1Yzc3NFx1YWNlMCAxICZsZTsgTGVuZ3RoKFcpICZsZTsgMSwwMDApPFwvbGk+XHJcblx0PGxpPlx1Yzc3NFx1YzViNFx1YzExYyBWXHVhYzFjIFx1YzkwNFx1YzVkMCBcdWFjMDEgXHVjMTM4XHViODVjIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4IHgsIHksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMyYjlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViMmY1XHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YjI5NCBcdWIyZThcdWM1YjQgV1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgeCwgeSAmbGU7IDEsMDAwIFx1Yzc3NFx1YWNlMCAxICZsZTsgTGVuZ3RoKFcpICZsZTsgMSwwMDApPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMFx1Yjg1YyBcdWIyZThcdWM1YjRcdWIwN2NcdWI5YWMgXHVjNzA0XHVjZTU4XHVhYzAwIFx1YWNiOVx1Y2U1OFx1YWM3MFx1YjA5OCBcdWMxMzhcdWI4NWMgXHViMmU4XHVjNWI0XHViMDdjXHViOWFjIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWFjYjlcdWNlNThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMzdjXHVjOTkwXHVkMzEwXHVjNzU4IFx1YzgxY1x1Yzc3YyBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1Yzc0MCB4ID0geSA9IDBcdWM3NzRcdWIyZTQuIHhcdWIyOTQgXHVhYzAwXHViODVjIFx1YzcwNFx1Y2U1OCwgeVx1YjI5NCBcdWMxMzhcdWI4NWMgXHVjNzA0XHVjZTU4XHViOTdjIFx1YWNiMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHViNjEwXHVkNTVjIFx1YWMwMFx1Yjg1YyBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YywgXHVjMTM4XHViODVjIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NDRcdWI3OTggXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzM2OFx1YjBiNFx1YjgyNFx1YzgzOCBcdWFjMDRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1Mzk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV3JvbmcgQW5zd2VyIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgYXJlIHNvbHZpbmcgYSBjcm9zc3dvcmQgcHV6emxlIGFuZCB5b3UgaGF2ZSBhbHJlYWR5IHdyaXR0ZW4gZG93biB0aGUgYW5zd2VycyB0byBhbGwgcXVlc3Rpb25zLiBXaGlsZSBmaWxsaW5nIGluIHRoZSBhbnN3ZXJzIGluIHRoZSBkaWFncmFtLCB5b3Ugbm90aWNlIHRoYXQgc29tZSBhbnN3ZXJzIGhhdmUgb3ZlcmxhcHBpbmcgbGV0dGVycyB0aGF0IGRvIG5vdCBtYXRjaCwgc28geW91IG11c3QgaGF2ZSBtYWRlIHNvbWUgbWlzdGFrZXMgaW4gdGhlIGFuc3dlcnMuIEluc3RlYWQgb2YgY2hlY2tpbmcgeW91ciBhbnN3ZXJzLCB5b3UgZGVjaWRlIHRvIHdyaXRlIGEgY29tcHV0ZXIgcHJvZ3JhbSB0byBmaW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBhbnN3ZXJzIHRoYXQgY291bGQgaGF2ZSBiZWVuIGNvcnJlY3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIHRlc3QgY2FzZSBoYXMgdGhlIGZvbGxvd2luZyBmb3JtYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgSCBhbmQgViAsIHNhdGlzZnlpbmcgMSAmbGU7IEgsViAmbGU7IDUwMDogdGhlIG51bWJlciBvZiBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCB3b3JkcywgcmVzcGVjdGl2ZWx5LjxcL2xpPlxyXG5cdDxsaT5IIGxpbmVzLCBvbmUgZm9yIGVhY2ggaG9yaXpvbnRhbCB3b3JkLCBlYWNoIHdpdGggdHdvIGludGVnZXJzIHggYW5kIHkgYW5kIGEgc3RyaW5nIFcsIHNhdGlzZnlpbmcgMCAmbGU7IHgseSAmbGU7IDEsIDAwMCBhbmQgMSAmbGU7IExlbmd0aChXKSAmbGU7IDEsIDAwMDogdGhlIGxvY2F0aW9uIG9mIHRoZSBmaXJzdCBsZXR0ZXIgYW5kIHRoZSBhbnN3ZXIuPFwvbGk+XHJcblx0PGxpPlYgbGluZXMsIG9uZSBmb3IgZWFjaCB2ZXJ0aWNhbCB3b3JkLCBlYWNoIHdpdGggdHdvIGludGVnZXJzIHggYW5kIHkgYW5kIGEgc3RyaW5nIFcsIHNhdGlzZnlpbmcgMCAmbGU7IHgseSAmbGU7IDEsIDAwMCBhbmQgMSAmbGU7IExlbmd0aChXKSAmbGU7IDEsIDAwMDogdGhlIGxvY2F0aW9uIG9mIHRoZSBmaXJzdCBsZXR0ZXIgYW5kIHRoZSBhbnN3ZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW50ZWdlcnMgYW5kIHN0cmluZ3Mgb24gdGhlIHNhbWUgbGluZSBhcmUgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIE5vIHBhaXIgb2YgaG9yaXpvbnRhbCB3b3JkcyB3aWxsIG92ZXJsYXAsIG5vciB3aWxsIGFueSBwYWlyIG9mIHZlcnRpY2FsIHdvcmRzLiBUaGUgd29yZHMgY29uc2lzdCBvZiB1cHBlciBjYXNlIGxldHRlcnMgb25seS48XC9wPlxyXG5cclxuPHA+VGhlIHRvcCBsZWZ0IGNvcm5lciBvZiB0aGUgZGlhZ3JhbSBpcyBhdCB4ID0geSA9IDAsIHggcnVucyBpbiB0aGUgaG9yaXpvbnRhbCBkaXJlY3Rpb24sIGFuZCB5IHJ1bnMgaW4gdGhlIHZlcnRpY2FsIGRpcmVjdGlvbiAoZG93bndhcmRzKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIGluIHRoZSBpbnB1dCwgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBudW1iZXIsIG9uIGEgc2luZ2xlIGxpbmU6IHRoZSBtYXhpbXVtIG51bWJlciBvZiBhbnN3ZXJzIHRoYXQgY2FuIGZpdCBpbiB0aGUgY3Jvc3N3b3JkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==