Purifying the Dark Master's Centipede

In a final battle against the Dark Master, our hero "Small Square" must purify the segments of the Dark Master's centipede. The centipede has n segments, each starting with a brightness of 1. A segment is considered purified when its brightness reaches a specified value k (i.e. it becomes exactly k).

Small Square has prepared m magical operation schemes. These schemes come in four types:

• Type 1: For a segment with brightness exactly a, change its brightness to b (note that b may be less than or equal to a).
• Type 2: For a segment with brightness in the interval \([a_1, a_2]\), change its brightness to b₁.
• Type 3: For a segment with brightness exactly a₁, change its brightness to any value in the interval \([b_1, b_2]\).
• Type 4: For a segment with brightness in the interval \([a_1, a_2]\), change its brightness to any value in the interval \([b_1, b_2]\).

Each scheme has an independent usage limit l, meaning that each scheme can be applied at most l times in total. Operations can be applied in any order and a segment may undergo a sequence of operations. Your task is to determine the maximum number of segments that Small Square can purify (i.e. reach exactly brightness k), given the initial n segments and the available schemes.

Note: If k is 1, then all segments are already purified.

This problem can be modeled as a max flow problem. Think of each segment as a unit of flow starting at brightness 1, and each scheme as a transformation edge with a limited number of uses. Some schemes allow a range of input values and a range of outputs—the key is to choose the correct transformation so that the flow reaches brightness k without exceeding the usage limits.

inputFormat

The input begins with a line containing three integers: n (1 ≤ n), the number of segments; k (k ≥ 1), the target brightness for purification; and m (m ≥ 1), the number of operation schemes.

Then follow m lines describing the schemes. Each line begins with an integer representing the scheme type (1, 2, 3, or 4), followed by the parameters:

• Type 1: 1 a b l
• Type 2: 2 a1 a2 b1 l
• Type 3: 3 a1 b1 b2 l
• Type 4: 4 a1 a2 b1 b2 l

All numbers are integers. It is guaranteed that the parameters and intervals are such that the transformation is well–defined.

Example:

5 5 2
3 1 3 5 3
1 1 3 5

outputFormat

Output a single integer: the maximum number of segments that can be purified (i.e. reach brightness exactly k).

Example Output for the above sample:

3

sample

5 5 2
3 1 3 5 3
1 1 3 5

3