Limits 2s, 512 MB

Charles Bridge - Masterpiece of Medieval Architecture in Prague - Amazing  CzechiaYou are walking at midnight along a road that has NN checkpoints numbered from 11 to NN 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 DD upon you which will be active till checkpoint xx. This blessing or curse will be in effect at all the checkpoints ii for sixs≤i≤x. If you receive a blessing of power DD, your health will increase by DD at each checkpoint where it is active. Conversely, if you receive a curse of power DD, your health will decrease by DD at each checkpoint where it is active.

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

If at any checkpoint (including checkpoint NN) 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 11 to NN? 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, TT (1T1000)(1 ≤ T ≤ 1000) which denotes the number of test cases.

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

  • typetype ss xx DD (1type2;(1 ≤ type ≤ 2; 1sxN;1 ≤ s ≤ x ≤ N; 1D104)1 ≤ D ≤ 10^4)

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

It is guaranteed that the sum of QQ over all test cases 2×105≤ 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!

Submit

Login to submit.

Statistics

57% Solution Ratio
tanzim_bnEarliest, Feb '23
naeem4265Fastest, 0.1s
adibur6Lightest, 5.5 MB
user.0039Shortest, 1056B
Toph uses cookies. By continuing you agree to our Cookie Policy.