시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 749 233 136 24.954%

문제

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

  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+XHVhYzhjXHVjNzg0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYWE5XHVkNDVjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YzlkMVx1YzViNFx1YWMwMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViYWE5XHVkNDVjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzk4OSwgXHVjMTIwXHViZDg0XHVjNzQ0IFx1YjljZVx1Yzc3NCBcdWM5ZDFcdWM1YjRcdWFjMDBcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjODEwXHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YjMwMFx1Yjg1YyBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzlkMVx1YzViNFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWQxXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWM2NDAsIFx1Y2Q1Y1x1YjMwMCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMFx1Yjg1YyBcdWMxMjBcdWM3NTggXHVjMjE4IG5cdWFjZmMgXHVjMTM4XHViODVjIFx1YzEyMFx1Yzc1OCBcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgbixtICZsZTsgMjAwKSBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWMwMFx1Yjg1YyBcdWMxMjBcdWM3NTggXHVjODE1XHViY2Y0IHgseSx4JiMzOTsseSYjMzk7LHdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoeCx5KVx1YzY0MCAoeCYjMzk7LHkmIzM5OylcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzU5MSBcdWIwNWQgXHVjODEwXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YWNlMCwgd1x1YjI5NCBcdWFkZjggXHVjMTIwXHViZDg0XHVjNzU4IFx1YmIzNFx1YWM4Y1x1Yzc3NFx1YjJlNC4gKHkgPSB5JiMzOTspIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMxMzhcdWI4NWMgXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWFjMDBcdWI4NWMgXHVjMTIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM1OTFcdWMyMThcdWM3NzRcdWFjZTAmbmJzcDsxMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHViYjM0XHVhYzhjXHViM2M0IFx1YzU5MVx1YzIxOFx1Yzc3NFx1YmE3MCZuYnNwOzIwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMxMjBcdWJkODQgXHVjMzBkXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzgxMFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWJhNzAsIFx1YjA1ZCBcdWM4MTBcdWM1ZDBcdWMxMWMgXHViOWNjXHViMDk4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViNDUwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWM4MTVcdWMyMThcdWIyOTQgXHVjOWQxXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTIwXHViZDg0XHVjNzU4IFx1YzMwZFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4XHViMjk0IFx1YWRmOCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOWNjXHVkMDdjXHVjNzQ0IFx1YzlkMVx1YzViNFx1YWMwMFx1YmE3NFx1YzExYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjODEwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg5OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaWNrdXAgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBwbGF5aW5nIGEgY29tcHV0ZXIgZ2FtZSBjYWxsZWQgdGhlICZxdW90O1BpY2t1cC4mcXVvdDsgVGhlIHJ1bGVzIGFyZSBhcyBmb2xsb3dzOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRoZXJlIGFyZSBhIG51bWJlciBvZiBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBsaW5lIHNlZ21lbnRzLiAoU2VlIHRoZSBmaWd1cmUgYmVsb3cuKSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5Zb3UgY2FuICZxdW90O1BpY2t1cCZxdW90OyBhIHBhaXIgb2YgbGluZSBzZWdtZW50cyBieSBjbGlja2luZyBvbiB0aGUgY3Jvc3NpbmcgbWFkZSBieSB0aGUgcGFpci4gKFRoZSBwYWlyIGRpc2FwcGVhcnMgZnJvbSBzY3JlZW4gd2hlbiB5b3UgZG8gdGhpcy4pJm5ic3A7PFwvbGk+XHJcblx0PGxpPkVhY2ggbGluZSBzZWdtZW50IGlzIGdpdmVuIGEgd2VpZ2h0LiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5XaGVuIHlvdSBwaWNrIHVwIGEgcGFpciB3aXRoIHdlaWdodHMgYSBhbmQgYiwgeW91IGFyZSBnaXZlbiBhIHNjb3JlIG9mIGEgJnRpbWVzOyBiLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbGluZXNlZy5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTNweDsgd2lkdGg6MjIxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDEuIEFuIEV4YW1wbGUgU2NyZWVuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBnb2FsIGlzIHRvIHBpY2sgdXAgdGhlIG1vc3QgbGluZSBzZWdtZW50cy4gVGhlIHNlY29uZCBnb2FsIGlzIHRvIG1heGltaXplIHRoZSB0b3RhbCBzY29yZS4gVGhhdCBpcywgaWYgdGhlcmUgYXJlIG1vcmUgdGhhbiBvbmUgd2F5IG9mIHBpY2tpbmcgdXAgdGhlIG1vc3QgbGluZSBzZWdtZW50cywgdGhlbiB5b3UgaGF2ZSB0byBmaW5kIHRoZSBvbmUgd2l0aCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBzY29yZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtLCBnaXZlbiB0aGUgc3BlY2lmaWNhdGlvbiBvZiBhbiBpbnN0YW5jZSBvZiB0aGUgZ2FtZSwgd2hpY2ggY29tcHV0ZXMgdGhlIG1heGltdW0gcG9zc2libGUgbnVtYmVyIG9mIGxpbmUgc2VnbWVudHMgdGhhdCBjYW4gYmUgcGlja2VkIHVwIGFuZCB0aGUgbWF4aW11bSBwb3NzaWJsZSBzY29yZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggaW50ZWdlcnMgbiBhbmQgbSwgdGhlIG51bWJlciBvZiBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBsaW5lIHNlZ21lbnRzLCByZXNwZWN0aXZlbHksIHdoZXJlIDEgJmxlOyBuLCBtICZsZTsgMjAwLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWlucyBmaXZlIGludGVnZXJzIHgseSx4JiMzOTsseSYjMzk7LHcsIHJlcHJlc2VudGluZyB0aGUgdHdvIGVuZHBvaW50cyAobm90ZSwgeSA9IHkmcHJpbWU7KSBhbmQgdGhlIHdlaWdodCBvZiBlYWNoIGhvcml6b250YWwgbGluZSBzZWdtZW50LiBBbHNvIGVhY2ggb2YgdGhlIGZvbGxvd2luZyBtIGxpbmVzIGNvbnRhaW5zIGFuIGFuYWxvZ291cyBpbmZvcm1hdGlvbiBmb3IgZWFjaCB2ZXJ0aWNhbCBsaW5lIHNlZ21lbnQuIEFsbCBjb29yZGluYXRlIHZhbHVlcyBhcmUgcG9zaXRpdmUgYW5kIGFyZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwLDAwMC4gVGhlIHdlaWdodHMgYXJlIGFsc28gcG9zaXRpdmUgYW5kIGFyZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMjAuIEFueSBwYWlyIG9mIGxpbmUgc2VnbWVudHMgbWF5IHNoYXJlIGF0IG1vc3Qgb25lIHBvaW50IHdoaWNoIGlzIG5ldmVyIGFuIGVuZHBvaW50IG9mIHRoZSBsaW5lIHNlZ21lbnRzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgZm9yIGVhY2ggdGVzdCBjYXNlLiBZb3Ugc2hvdWxkIG91dHB1dCB0aGUgbWF4aW11bSBwb3NzaWJsZSBudW1iZXIgb2YgbGluZSBzZWdtZW50IHBhaXJzIHRoYXQgY2FuIGJlIHBpY2tlZCB1cCwgZm9sbG93ZWQgYnkgbWF4aW11bSBwb3NzaWJsZSBzY29yZSB3aGlsZSBwaWNraW5nIHVwIHRoZSBtb3N0IHBhaXJzIG9mIGxpbmUgc2VnbWVudHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d