Kakuro Puzzle Difficulty

You are given a Kakuro puzzle. In this puzzle, each white cell must be filled with an integer from 1 to k. Some white cells are linked by clues. Each clue covers a contiguous group of white cells either horizontally or vertically. A clue is given as a sum s for a group of c cells. Under the clue restriction, the valid assignments for that group are all c-tuples of distinct numbers chosen from 1 to k whose sum is s. The candidate set for a group is defined as the union of all numbers appearing in any valid c-tuple.

Every white cell is associated with either one or two clues (usually one horizontal and one vertical). The candidate set for a white cell is the intersection of the candidate sets coming from all groups that contain that cell. (If a cell appears in only one group, its candidate set is just that group’s candidate set.)

The difficulty of a Kakuro puzzle is defined as the sum, over all white cells, of the number of candidates (the size of the candidate set) for that cell – only based on the initial clues (i.e. no propagation or deduction is performed).

Input Format:

• The first line contains two integers: k (the maximum digit allowed) and m (the number of clue groups).
• Each of the next m lines describes a clue group in the following format:
  D c s r1 c1 r2 c2 ... r_c c_c
  where D is a character 'H' or 'V' representing a Horizontal or Vertical clue respectively, c (≥1) is the number of white cells in the group, s is the clue sum, and (r_i, c_i) are the 1-indexed coordinates of the white cells in that group.

It is guaranteed that every white cell appears in at least one group. For a white cell that appears in two groups, its candidate set is the intersection of the candidate sets from the corresponding groups. The goal is to compute the puzzle difficulty which is the sum of the sizes of the candidate sets over all white cells.

Note on Computing a Group's Candidate Set:
For a group of c cells with clue sum s, consider all selections of c distinct numbers from {1, 2, …, k} whose sum equals s. The candidate set is the union of all numbers appearing in any such combination. For example, if c = 4 and s = 10, then the only possibility is {1, 2, 3, 4}, so the candidate set is {1, 2, 3, 4}.

Example:
Consider the following groups (with k = 9):
• Group 1 (Horizontal): H 2 16 2 2 2 3 covers cells (2,2) and (2,3). The only valid assignment is {7,9} (in some order), so its candidate set is {7,9}.
• Group 2 (Vertical): V 3 23 2 2 3 2 4 2 covers cells (2,2), (3,2), (4,2). Its candidate set is {6,8,9}.
• Group 3 (Vertical): V 2 15 2 3 3 3 covers cells (2,3) and (3,3). Its candidate set is {6,7,8,9} (all pairs from 1..9 that sum to 15 yield this union when digits are distinct, e.g. (6,9) and (7,8)).
• Group 4 (Horizontal): H 2 9 3 2 3 3 covers cells (3,2) and (3,3). For two cells summing to 9, the candidate set is the union of all valid pairs, which is {1,2,3,4,5,6,7,8}.
• Group 5 (Horizontal): H 1 8 4 2 covers cell (4,2). For a single cell, the only possibility is the number 8, so its candidate set is {8}.
Then, the candidate set for each white cell is computed as follows:
- Cell (2,2) appears in Group 1 and Group 2, so its candidates are {7,9} ∩ {6,8,9} = {9} (size 1).
- Cell (2,3) appears in Group 1 and Group 3, so its candidates are {7,9} ∩ {6,7,8,9} = {7,9} (size 2).
- Cell (3,2) appears in Group 2 and Group 4, so its candidates are {6,8,9} ∩ {1,2,3,4,5,6,7,8} = {6,8} (size 2).
- Cell (3,3) appears in Group 3 and Group 4, so its candidates are {6,7,8,9} ∩ {1,2,3,4,5,6,7,8} = {6,7,8} (size 3).
- Cell (4,2) appears in Group 2 and Group 5, so its candidates are {6,8,9} ∩ {8} = {8} (size 1).
Thus, the puzzle difficulty is 1 + 2 + 2 + 3 + 1 = 9.

inputFormat

The input begins with a single line containing two integers k and m (1 ≤ k ≤ 50, m ≥ 1), where k is the maximum digit and m is the number of clue groups. The following m lines each contain a clue group in the following format:

D c s r1 c1 r2 c2 ... rc cc

Here, D is either 'H' or 'V' indicating a horizontal or vertical clue, c (≥1) is the number of white cells in that group, s is the clue sum, and each pair (ri, ci) (1-indexed) represents the coordinates of a white cell. It is guaranteed that every white cell appears in at least one group.

outputFormat

Output a single integer, the difficulty of the puzzle, i.e. the sum of the sizes of the candidate sets over all white cells.

sample

9 5
H 2 16 2 2 2 3
V 3 23 2 2 3 2 4 2
V 2 15 2 3 3 3
H 2 9 3 2 3 3
H 1 8 4 2

9