시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 816 272 147 25.835%

문제

명우는 픽업 게임을 하려고 한다. 규칙은 다음과 같다.

  1. 아래 그림과 같은 가로, 세로 선이 여러 개 있다.
  2. 선분의 교점을 클릭하면 교점을 이루는 두 선분을 집어갈 수 있다. (집어가면 두 선분은 사라진다)
  3. 모든 선분은 무게가 있다.
  4. 무게가 a와 b인 선분을 집어갈 때, 얻는 점수는 a × b이다.

게임의 첫 번째 목표는 최대한 많은 선분을 집어가는 것이다. 두 번째 목표는 최대한 많은 점수를 얻는 것이다. 즉, 선분을 많이 집어가는 방법이 여러 가지라면, 점수를 최대로 하는 방법으로 집어가야 한다.

게임의 정보가 주어졌을 때, 집을 수 있는 선분의 최대 개수와, 최대 점수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 가로 선의 수 n과 세로 선의 수 m이 주어진다. (1 ≤ n,m ≤ 200) 다음 n개 줄에는 각 가로 선의 정보 x,y,x',y',w가 주어진다. (x,y)와 (x',y')는 선분의 양 끝 점을 나타내고, w는 그 선분의 무게이다. (y = y') 다음 m개 줄에는 세로 선의 정보가 가로 선의 정보와 같은 형식으로 주어진다. 모든 좌표는 양수이고 100,000보다 작거나 같다. 또한, 무게도 양수이며 20보다 작거나 같다. 모든 선분 쌍은 최대 한 개의 점에서 만나며, 끝 점에서 만나는 경우는 없다.

출력

각 테스트 케이스마다 두 정수를 출력한다. 첫 정수는 집을 수 있는 선분의 쌍의 개수의 최댓값이고, 두 번째는 그 쌍의 개수만큼을 집어가면서 얻을 수 있는 최대 점수이다.

예제 입력 1

2
2 2
1 2 4 2 1
1 3 4 3 2
2 1 2 4 3
3 1 3 4 4
2 2
1 2 5 2 3
7 2 6 2 3
2 3 2 1 2
3 1 3 3 1

예제 출력 1

2 11
1 6
W3sicHJvYmxlbV9pZCI6Ijg5OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWFlMzAgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhODVcdWM2YjBcdWIyOTQgXHVkNTNkXHVjNWM1IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZGNcdWNlNTlcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YyBcdWMxMjBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWFkNTBcdWM4MTBcdWM3NDQgXHVkMDc0XHViOWFkXHVkNTU4XHViYTc0IFx1YWQ1MFx1YzgxMFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHViNDUwIFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWM5ZDFcdWM1YjRcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzlkMVx1YzViNFx1YWMwMFx1YmE3NCBcdWI0NTAgXHVjMTIwXHViZDg0XHVjNzQwIFx1YzBhY1x1Yjc3Y1x1YzljNFx1YjJlNCk8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1YzEyMFx1YmQ4NFx1Yzc0MCBcdWJiMzRcdWFjOGNcdWFjMDAgXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJiMzRcdWFjOGNcdWFjMDAgYVx1YzY0MCBiXHVjNzc4IFx1YzEyMFx1YmQ4NFx1Yzc0NCBcdWM5ZDFcdWM1YjRcdWFjMDggXHViNTRjLCBcdWM1YmJcdWIyOTQgXHVjODEwXHVjMjE4XHViMjk0IGEgJnRpbWVzOyBiXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbGluZXNlZy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTNweDsgd2lkdGg6MjIxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYWE5XHVkNDVjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YzlkMVx1YzViNFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYWE5XHVkNDVjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YjljZVx1Yzc3NCBcdWM5ZDFcdWM1YjRcdWFjMDBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWI3N2NcdWJhNzQsIFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWIzMDBcdWI4NWMgXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWM5ZDFcdWM1YjRcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzlkMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHVjNjQwLCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDBcdWI4NWMgXHVjMTIwXHVjNzU4IFx1YzIxOCBuXHVhY2ZjIFx1YzEzOFx1Yjg1YyBcdWMxMjBcdWM3NTggXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4sbSAmbGU7IDIwMCkgXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWFjMDBcdWI4NWMgXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNCB4LHkseCYjMzk7LHkmIzM5Oyx3XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHgseSlcdWM2NDAgKHgmIzM5Oyx5JiMzOTspXHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWM1OTEgXHViMDVkIFx1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIHdcdWIyOTQgXHVhZGY4IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWJiMzRcdWFjOGNcdWM3NzRcdWIyZTQuICh5ID0geSYjMzk7KSBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4XHViODVjIFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVhYzAwXHViODVjIFx1YzEyMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNTkxXHVjMjE4XHVjNzc0XHVhY2UwJm5ic3A7MTAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YmIzNFx1YWM4Y1x1YjNjNCBcdWM1OTFcdWMyMThcdWM3NzRcdWJhNzAmbmJzcDsyMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjMTIwXHViZDg0IFx1YzMwZFx1Yzc0MCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM1ZDBcdWMxMWMgXHViOWNjXHViMDk4XHViYTcwLCBcdWIwNWQgXHVjODEwXHVjNWQwXHVjMTFjIFx1YjljY1x1YjA5OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNjYWIgXHVjODE1XHVjMjE4XHViMjk0IFx1YzlkMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzEyMFx1YmQ4NFx1Yzc1OCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOFx1YjI5NCBcdWFkZjggXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjljY1x1ZDA3Y1x1Yzc0NCBcdWM5ZDFcdWM1YjRcdWFjMDBcdWJhNzRcdWMxMWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzgxMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4OTkyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGlja3VwIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgcGxheWluZyBhIGNvbXB1dGVyIGdhbWUgY2FsbGVkIHRoZSAmcXVvdDtQaWNrdXAuJnF1b3Q7IFRoZSBydWxlcyBhcmUgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGVyZSBhcmUgYSBudW1iZXIgb2YgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgbGluZSBzZWdtZW50cy4gKFNlZSB0aGUgZmlndXJlIGJlbG93LikmbmJzcDs8XC9saT5cclxuXHQ8bGk+WW91IGNhbiAmcXVvdDtQaWNrdXAmcXVvdDsgYSBwYWlyIG9mIGxpbmUgc2VnbWVudHMgYnkgY2xpY2tpbmcgb24gdGhlIGNyb3NzaW5nIG1hZGUgYnkgdGhlIHBhaXIuIChUaGUgcGFpciBkaXNhcHBlYXJzIGZyb20gc2NyZWVuIHdoZW4geW91IGRvIHRoaXMuKSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5FYWNoIGxpbmUgc2VnbWVudCBpcyBnaXZlbiBhIHdlaWdodC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+V2hlbiB5b3UgcGljayB1cCBhIHBhaXIgd2l0aCB3ZWlnaHRzIGEgYW5kIGIsIHlvdSBhcmUgZ2l2ZW4gYSBzY29yZSBvZiBhICZ0aW1lczsgYi48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xpbmVzZWcucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjEzcHg7IHdpZHRoOjIyMXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBBbiBFeGFtcGxlIFNjcmVlbiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgZ29hbCBpcyB0byBwaWNrIHVwIHRoZSBtb3N0IGxpbmUgc2VnbWVudHMuIFRoZSBzZWNvbmQgZ29hbCBpcyB0byBtYXhpbWl6ZSB0aGUgdG90YWwgc2NvcmUuIFRoYXQgaXMsIGlmIHRoZXJlIGFyZSBtb3JlIHRoYW4gb25lIHdheSBvZiBwaWNraW5nIHVwIHRoZSBtb3N0IGxpbmUgc2VnbWVudHMsIHRoZW4geW91IGhhdmUgdG8gZmluZCB0aGUgb25lIHdpdGggdGhlIGxhcmdlc3QgcG9zc2libGUgc2NvcmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSwgZ2l2ZW4gdGhlIHNwZWNpZmljYXRpb24gb2YgYW4gaW5zdGFuY2Ugb2YgdGhlIGdhbWUsIHdoaWNoIGNvbXB1dGVzIHRoZSBtYXhpbXVtIHBvc3NpYmxlIG51bWJlciBvZiBsaW5lIHNlZ21lbnRzIHRoYXQgY2FuIGJlIHBpY2tlZCB1cCBhbmQgdGhlIG1heGltdW0gcG9zc2libGUgc2NvcmUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGludGVnZXJzIG4gYW5kIG0sIHRoZSBudW1iZXIgb2YgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgbGluZSBzZWdtZW50cywgcmVzcGVjdGl2ZWx5LCB3aGVyZSAxICZsZTsgbiwgbSAmbGU7IDIwMC4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgZml2ZSBpbnRlZ2VycyB4LHkseCYjMzk7LHkmIzM5Oyx3LCByZXByZXNlbnRpbmcgdGhlIHR3byBlbmRwb2ludHMgKG5vdGUsIHkgPSB5JnByaW1lOykgYW5kIHRoZSB3ZWlnaHQgb2YgZWFjaCBob3Jpem9udGFsIGxpbmUgc2VnbWVudC4gQWxzbyBlYWNoIG9mIHRoZSBmb2xsb3dpbmcgbSBsaW5lcyBjb250YWlucyBhbiBhbmFsb2dvdXMgaW5mb3JtYXRpb24gZm9yIGVhY2ggdmVydGljYWwgbGluZSBzZWdtZW50LiBBbGwgY29vcmRpbmF0ZSB2YWx1ZXMgYXJlIHBvc2l0aXZlIGFuZCBhcmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDEwMCwwMDAuIFRoZSB3ZWlnaHRzIGFyZSBhbHNvIHBvc2l0aXZlIGFuZCBhcmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIDIwLiBBbnkgcGFpciBvZiBsaW5lIHNlZ21lbnRzIG1heSBzaGFyZSBhdCBtb3N0IG9uZSBwb2ludCB3aGljaCBpcyBuZXZlciBhbiBlbmRwb2ludCBvZiB0aGUgbGluZSBzZWdtZW50cy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIGZvciBlYWNoIHRlc3QgY2FzZS4gWW91IHNob3VsZCBvdXRwdXQgdGhlIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIGxpbmUgc2VnbWVudCBwYWlycyB0aGF0IGNhbiBiZSBwaWNrZWQgdXAsIGZvbGxvd2VkIGJ5IG1heGltdW0gcG9zc2libGUgc2NvcmUgd2hpbGUgcGlja2luZyB1cCB0aGUgbW9zdCBwYWlycyBvZiBsaW5lIHNlZ21lbnRzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==