우승하는 경우의 수

면접 대비

시간 제한1초메모리 제한128 MB

요약

네 팀 중 일부 경기 결과가 주어졌을 때, 남은 경기 결과의 모든 경우 중 팀 T가 다른 모든 팀보다 엄격히 많은 점수로 우승하는 경우의 수를 센다.

난이도: 쉬움10점 중 3점
유형: 완전 탐색, 구현, 시뮬레이션, 조합론
정답자: 아직 제출이 없습니다

문제

응원하는 팀이 작은 토너먼트에서 우승할 가능성을 알고 싶습니다.

토너먼트에는 정확히 네 팀이 참가합니다. 대회가 끝나면 각 팀이 나머지 세 팀과 한 번씩 맞붙어 총 여섯 경기가 열립니다. 각 경기는 한 팀이 이기고 다른 팀이 지거나, 무승부로 끝납니다. 무승부가 아니라면 이긴 팀은 승점 $3$ 점, 진 팀은 $0$ 점을 얻습니다. 무승부라면 두 팀 모두 승점 $1$ 점씩 얻습니다.

응원하는 팀은 최종 승점이 다른 모든 팀보다 엄격히 많을 때에만 우승합니다. 즉, 승점이 같아 공동 $1$ 위가 되는 경우에는 우승으로 인정하지 않습니다.

토너먼트는 아직 끝나지 않았지만, 이미 치른 경기의 결과는 모두 알고 있습니다. 아직 치르지 않은 남은 경기들에서 승점이 배분될 수 있는 모든 경우를 고려하여, 그중 응원하는 팀이 우승하는 경우가 몇 가지인지 구하세요.

입력

첫째 줄에 응원하는 팀의 번호 $T$ ( $1 \le T \le 4$ )가 주어집니다. 둘째 줄에 이미 치른 경기 수 $G$ ( $0 \le G \le 5$ )가 주어집니다. 이어지는 $G$ 개의 줄에는 이미 치른 경기의 결과가 주어지며, 각 줄에는 네 정수 $A$ , $B$ , $S_A$ , $S_B$ 가 공백으로 구분되어 주어집니다 ( $1 \le A < B \le 4$ , $S_A, S_B \ge 0$ ). 이는 팀 $A$ (점수 $S_A$ )와 팀 $B$ (점수 $S_B$ )의 경기를 뜻하며, $S_A > S_B$ 이면 팀 $A$ 가 이기고, $S_A < S_B$ 이면 팀 $B$ 가 이기며, $S_A = S_B$ 이면 무승부입니다. 같은 두 팀은 두 번 맞붙지 않으므로, 입력으로 주어지는 $(A, B)$ 쌍은 모두 서로 다릅니다.

출력

남은 경기들에 승점이 배분되는 모든 경우 중에서 팀 $T$ 가 우승하는 경우의 수를 정수 하나로 출력합니다.

예제2

예제 1
입력
```
3
3
1 3 7 5
3 4 0 8
2 4 2 2
```
예상 출력
```
0
```
예제 2
입력
```
3
4
1 3 5 7
3 4 8 0
2 4 2 2
1 2 5 5
```
예상 출력
```
9
```