시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 2521 467 310 18.430%

문제

유명한 피타고라스의 정리와 유사한 형태의 피타고라스 기대값 (Pythagorean Expectation)이 야구와 같은 스포츠 경기에 자주 사용된다. 피타고라스 기대값은 빌 제임스(Bill James)에 의해 정의되었으며, 이 값은 특정 야구팀이 한 시즌 동안 얼마나 잘 했는지를 평가하는 지표 중 하나로 사용된다. 한 야구팀의 피타고라스 기대값 \(W\)는 아래 식과 같이 정의된다.

\(W = \dfrac{S^2}{S^2 + A^2}\),

여기서 \(S\)는 해당 팀의 총 득점 수를, \(A\)는 해당 팀의 총 실점 수를 나타낸다.

이 기대값을 실제 승률과 비교하여, 해당 팀이 한 시즌을 얼마나 잘 보냈는지 평가할 수 있다. 예를 들어, 한화 이글스는 2014 시즌에 619 득점과 889 실점을 했다. 즉, \(S\) = 619, \(A\) = 889이 되어, 한화 팀의 피타고라스 기대값은 \(W\) = 6192/(6192 + 8892) = 0.326이 된다. KBO 규정에 따르면, 한 시즌당 한 팀은 128번의 경기를 해야 하므로, 한화는 0.326 ×128 = 41.728 경기에서는 승리했어야 한다. 실제 한화는 49경기에서 승리했기 때문에, 2014 시즌을 그리 나쁘지 않게 보냈음을 알 수 있다. 반면에 롯데 자이언츠는 \(S\) = 715이고, \(A\) = 719이 되어, \(W\) = 0.497이 된다. 따라서 0.497 ×128 = 63.616경기 이상을 이길 것으로 기대되었지만, 실제론 58경기만 승리했다. 결국, 롯데에게 2014년은 기대에 많이 못 미친 시즌이었음을 알 수 있다.

\(n\)개의 팀에 대한 기록이 주어지면, 이 기록으로부터 팀 별 피타고라스 기대값을 계산한 후, 그 중 최대 기대값과 최소 기대값을 출력하는 프로그램을 작성하시오.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 줄에는 두 양의 정수 \(n\) (2 ≤ \(n\) ≤ 1,000)과 \(m\) (2 ≤ \(m\) ≤ 1,000)이 주어진다. 여기서, \(n\)은 팀 개수이며, \(m\)은 전체 경기 수이다. 다음의 \(m\)개의 줄에는 각 경기에 대한 정보가 주어진다. 하나의 경기는 네 개의 정수 \(a\), \(b\), \(p\), \(q\)로 주어지는데, 팀 a와 팀 b가 경기를 했고, 팀 a는 p득점을 팀 b는 q득점을 했다는 의미이다. 여기서, 1 ≤ \(a\) ≠ \(b\) ≤ \(n\)이며, \(p\)와 \(q\)는 모두 음이 아닌 20 이하의 정수이다. 하나의 테스트 데이터에서 팀 당 경기수가 반드시 같을 필요는 없다. 만약, 어떤 팀의 총 득점과 총 실점이 모두 0이라면, 그 팀의 기대값은 0으로 정의한다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 두 정수 값을 한 줄에 하나씩 출력해야 한다. 첫 번째 줄에는 최대 피타고라스 기대값에 1,000을 곱한 값의 정수부분을 출력하고, 두 번째 줄에는 최소 피타고라스 기대값에 1,000을 곱한 값의 정수부분을 출력한다.

예제 입력

2
3 5
1 2 3 5
1 3 10 1
1 2 0 7
2 3 9 3
3 2 4 5
4 6
1 2 0 11
1 3 17 13
1 4 17 1
2 3 7 12
2 4 19 17
3 4 17 0

예제 출력

871
100
753
103

힌트