Background

Recently, $\rm$ has been playing a very fun game where he places energy emitters to attack enemy ships. However, $\rm$ is quite clumsy and brainless, always failing to pass even the simplest levels, so he wants your help.

Problem Description

In this game, you have $k$ $\alpha$ energy emitter activators that can activate any $k$ $\alpha$ emitters on an initial platform. These $\alpha$ emitters will then emit energy beams in the direction of north-east $45^\circ$, with an energy value of $\alpha_i$. There are $n$ floating platforms in the field, some of which are equipped with either $\alpha$ or $\beta$ emitters, with the following functionalities:

• For $\alpha$ emitters, if placed above a platform, they emit energy beams in the north-east $45^\circ$ direction with an energy value of $\alpha_i$; if placed below, they emit in the south-east $45^\circ$ direction with the same energy value.

• For $\beta$ emitters, regardless of their placement, they emit energy beams simultaneously in both north-east $45^\circ$ and south-east $45^\circ$ directions with an energy value of $\beta_i$.

However, the emitters on the floating platforms do not activate on their own; they only activate when hit by an energy beam. The emitter then emits an energy beam of a predetermined value. Note that a beam hitting these platforms will only activate the emitter if the beam's path does not already contain energy from the hit platform. Each hit activates the emitter once, and it will not re-emit if hit again by the same beam (i.e., energy does not stack again).

You can only activate $k$ $\alpha$ emitters on the initial platform at the beginning (these $k$ emitters are activated sequentially, each emitting once, but other emitters can emit multiple times).

The map is abstracted as a two-dimensional Cartesian coordinate system, where the line $x=0$ represents the ground (beams hitting the ground disappear, but if there's a platform on the ground, it will hit the platform first). All platforms, including the initial platform, are parallel to the $x$-axis. The enemy ship can be considered as a vertical line segment with endpoints $(wx, sy)$ and $(wx, ty)$. When a beam hits the ship, it takes damage equal to the sum of the energy values along the beam's path, and the beam then disappears. (Beams hitting other platforms do not bounce but are absorbed to activate the emitters).

Your task is to determine which initial $\alpha$ emitters to activate to maximize the damage to the ship, and find this maximum value.

Input Format

The first line contains two positive integers $k$ and $n$, representing the number of initial emitters you can activate and the total number of platforms, respectively.
The second line contains four integers $x_1, x_2, y, v$, indicating the initial platform's position, where each integer point on the platform has an $\alpha$ emitter capable of emitting an initial energy beam of value $v$.
The third line contains three integers $wx, sy, ty$, representing the enemy ship's position.
The next $n$ lines describe each platform, with the following formats:

• $0\ x_l\ x_r\ y$ represents an empty platform.
• $1\ x_l\ x_r\ y\ x_p\ w_i\ 0/1$ represents an $\alpha$ emitter at position $(x_p, y)$ on the platform $(x_l, y) \sim (x_r, y)$, emitting energy $w_i$, with the last $0$ or $1$ indicating whether it's above or below the platform ($0$ for above, $1$ for below).
• $2\ x_l\ x_r\ y\ x_p\ w_i$ represents a $\beta$ emitter at position $(x_p, y)$ on the platform $(x_l, y) \sim (x_r, y)$, emitting energy $w_i$.

Output Format

A single integer representing the maximum damage value.

Sample Input and Output

Input Sample #1

1 3
1 2 1 5
8 1 7
1 4 5 3 5 5 0
2 4 5 5 5 5
1 5 6 6 6 5 1

Output Sample #1

25

Input Sample #2

1 11
0 2 1 10
17 3 11
0 1 2 6
1 3 5 5 4 30 0
1 4 7 4 6 10 1
2 4 8 7 6 14
1 7 10 2 9 10 0
1 8 11 10 9 14 1
1 11 13 7 12 10 0
2 11 13 5 12 14
1 11 13 1 12 10 0
2 13 14 8 14 6
1 13 15 3 14 10 0

Output Sample #2

242

Notes

Sample Explanation:

For Sample 1, the optimal solution is the orange beam with a damage of $25$, while the green beam has a damage of $10$.

For Sample 2, only the orange beam delivers a damage of $242$, while the other two beams deliver only $98$.

Data Range:

• For $30\%$ of the data, $0 \leq n \leq 20, 1 \leq k \leq 3$;
• For $40\%$ of the data, the total length of all platforms (excluding the ship) does not exceed $10^6$;
• For $60\%$ of the data, $0 \leq n \leq 200, 1 \leq k \leq 50$;
• For $70\%$ of the data, $0 \leq n \leq 2000, 1 \leq k \leq 2000$;
• For $100\%$ of the data, $0 \leq n \leq 20000, 0 \leq k \leq 20000$, coordinates $0 \leq y \leq 10^9$, coordinates $0 \leq x \leq 10^9$, all energy values are within $0 \sim 10^4$, and each emitter is guaranteed to be on a platform, with platform and ship lengths at least $1$. The initial platform's length does not exceed $10^5$, and no platforms overlap;
• An additional $20\%$ of the data is the same as $100\%$, but with $n \leq 10^6$;

The input is large, so it is recommended to use fast input methods.

见题面 Input 部分

见题面 Output 部分