# Angels and Demons

National Girls' Programmi...
Limits 2s, 512 MB

You are walking at midnight along a road that has $N$ checkpoints numbered from $1$ to $N$ from left to right. Each checkpoint may be empty, or it may have angels or demons stationed there. If a checkpoint has an angel or demon, they will cast a blessing or curse of power $D$ upon you which will be active till checkpoint $x$. This blessing or curse will be in effect at all the checkpoints $i$ for $s≤i≤x$. If you receive a blessing of power $D$, your health will increase by $D$ at each checkpoint where it is active. Conversely, if you receive a curse of power $D$, your health will decrease by $D$ at each checkpoint where it is active.

Formally, if an angel with power $D$ is stationed at checkpoint $s$ and has an endpoint at checkpoint $x$, then for each checkpoint $i$ $(s ≤ i ≤ x)$ your health will increase by $D$. On the other hand if an demon with power $D$ is stationed at checkpoint $s$ and has an endpoint at checkpoint $x$, then for each checkpoint $i$ $(s ≤ i ≤ x)$ your health will decrease by $D$.

If at any checkpoint (including checkpoint $N$) your health becomes zero or negative, you will die. What is the minimum health you need to start with, to survive the walk from checkpoint $1$ to $N$? Please note here, the initial health must always be an integer value.

Note that there may be multiple angels and/or demons stationed at some checkpoints, and angels are slightly more powerful than demons. So if both angels and demons are active at a checkpoint, then all the blessings will take effect first, followed by the curses. Please refer to the explanation of the sample for better understanding.

## Input

The first line of the input will contain an integer, $T$ $(1 ≤ T ≤ 1000)$ which denotes the number of test cases.

Each of the test cases starts with two integers, $N$ $(1 ≤ N ≤ 10^9)$ and $Q$ $(1 ≤ Q ≤ 2\times10^5)$ describing the number of checkpoints and the total number of demons and angels. Then there will be $Q$ lines. Each of the next $Q$ lines will contain four integers separated by spaces in the following format describing the parameters for an angel or a demon:

• $type$ $s$ $x$ $D$ $(1 ≤ type ≤ 2;$ $1 ≤ s ≤ x ≤ N;$ $1 ≤ D ≤ 10^4)$

If $type = 1$ then it is an angel, otherwise it is a demon. $D, ~s, ~x$ describes the power of the blessing/curse and the active region of the blessing/curse.

It is guaranteed that the sum of $Q$ over all test cases $≤ 2 \times 10^5$.

## Output

For each test case, output a single integer, the minimum amount of health needed to survive the walk.

## Sample

InputOutput
1
10 3
2 1 3 2
1 1 2 2
1 2 3 1

1


Explanation of the sample:

You start with health 1. It can be shown that you cannot start with any integer health value lesser than this and be alive while completing the journey.

At checkpoint 1 first you get a blessing of power 2, your health becomes 3, then you get a curse of power 2 and your health drops to 1.

At checkpoint 2 first you get two blessings of power 1 and 2, your health becomes 1 + 1 + 2 = 4, then you get a curse of power 2, your health becomes 2.

At checkpoint 3, first you get a blessing of power 1, your health becomes 3, then you get a curse of power 2, your health becomes 1.

Then you continue with health 1 to checkpoint 10 to finish your journey. You didn’t die and you made it to the end! Congrats!