Chances of Winning

Interview

Time limit1sMemory limit128 MB

Summary

Given results of some games among four teams, count the outcomes of the remaining games where team T ends with strictly more points than every other team.

Level: Easy3 of 10
Topics: Brute force, Implementation, Simulation, Combinatorics
Solved: No attempts yet

Problem

You want to find out the chances that your favourite team becomes the champion of a small tournament.

There are exactly four teams. By the end of the tournament, six games will have been played, with each team playing every other team exactly once. Each game either has one team win and the other lose, or ends in a tie. If a game is not a tie, the winning team is awarded $3$ points and the losing team $0$ . If the game is a tie, each team is awarded $1$ point.

Your favourite team becomes the champion only if it finishes with strictly more total points than every other team. In other words, being tied for first place is not good enough.

The tournament is not over yet, but you know the results of every game that has already been played. Considering all possible ways points could be awarded in the remaining, not-yet-played games, determine in how many of those cases your favourite team is the champion.

Input

The first line contains an integer $T$ , your favourite team ( $1 \le T \le 4$ ). The second line contains an integer $G$ , the number of games already played ( $0 \le G \le 5$ ). Each of the next $G$ lines describes a played game with four space-separated integers $A$ , $B$ , $S_A$ , $S_B$ ( $1 \le A < B \le 4$ and $S_A, S_B \ge 0$ ). This means team $A$ (with score $S_A$ ) played team $B$ (with score $S_B$ ): team $A$ won if $S_A > S_B$ , team $B$ won if $S_A < S_B$ , and the game was a tie if $S_A = S_B$ . No pair of teams plays twice, so the pairs $(A, B)$ given in the input are all distinct.

Output

Output a single integer: the number of ways, over all possible outcomes of the remaining games, in which team $T$ is the tournament champion.

Examples2

Example 1
Input
```
3
3
1 3 7 5
3 4 0 8
2 4 2 2
```
Expected output
```
0
```
Example 2
Input
```
3
4
1 3 5 7
3 4 8 0
2 4 2 2
1 2 5 5
```
Expected output
```
9
```