| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 325 | 131 | 100 | 39.062% |
Albert는 수업 기말고사로 $N$점의 미술 작품을 전시해야 하는데 $M$명의 심사위원이 이를 평가할 예정이다. $N$점의 작품은 좌측에서 우측으로 나란히 진열되어야 하고, Albert는 이 순서를 자신이 임의로 정할 수 있다. 편의상 작품은 1번부터 $N$번까지 번호가 붙어있고, 심사위원도 1번부터 $M$번까지 번호가 붙어있다.
$j$번째 심사위원은 Albert에게 세 정수 $V_j, A_j, B_j$를 알려주는데, 만약 $A_j$번 작품이 $B_j$번 작품보다 왼쪽에 진열되면 $V_j$점을 주고 그렇지 않으면 0점을 준다는 의미이다. Albert의 기말고사 총 점수는 모든 심사위원이 부여한 점수의 총합이 된다.
예를 들어 $N = 3,ドル $M = 4,ドル $V = [1, 1, 1, 1],ドル $A = [1, 2, 1, 2],ドル $B = [2, 1, 3, 3]$ 이라 하자.
이 경우 Albert가 받을 수 있는 최대 점수는 3점이고, 총 2가지 다른 방법으로 작품을 진열하여 이 점수를 받아낼 수 있다.
입력으로 $N, M, V, A, B$가 주어졌을 때, Albert가 달성할 수 있는 최대 점수와, 그 점수를 달성할 수 있는 전시 방법의 수를 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. 다음 $M$줄에 걸쳐 각 줄에 $j$번째 심사위원의 평가 기준인 $V_j, A_j, B_j$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답인 두 정수를 공백으로 구분하여 각 줄에 출력한다.
첫 번째 정수는 Albert가 달성할 수 있는 최대 점수이고 두 번째 정수는 이를 달성할 수 있는 방법의 수이다.
3 3 3 3 1 3 2 3 2 2 2 1 3 4 1 1 2 1 2 1 1 1 3 1 2 3 4 3 10 2 4 5 4 3 1 4 3
5 2 3 2 16 4
예제 1: 작품을 1, 3, 2 순서로 전시하거나 2, 1, 3 순서로 전시하면 총 5점을 받을 수 있다.
예제 2: 본문에서 다루었다.
예제 3: 16점을 받을 수 있는 방법은 다음과 같이 네 가지 존재한다: 1, 2, 4, 3 순으로 전시, 2, 1, 4, 3 순으로 전시, 2, 4, 1, 3 순으로 전시, 혹은 2, 4, 3, 1 순으로 전시.