RGPC '18 P3 - Chocolate Day - Olympiads Online Judge

RGPC '18 P3 - Chocolate Day

Points: 10

Time limit: 1.4s

Memory limit: 128M

Authors:

Problem types

Valentine's Day, which coincidentally falls on the same day as the CCC this year, is rapidly approaching! You, having sorted out your priorities, are preparing sweets to give out to your classmates. You have $N$ ~N~ cups numbered in order from $1$ ~1~ to $N$ ~N~, and you fill them $T$ ~T~ times. More specifically, for each filling, you add $c$ ~c~ chocolates to all the cups between cup $a$ ~a~ and cup $b$ ~b~ inclusive.

However, before you spread happiness throughout the classroom, you decide to give some chocolates to your "special someone" before anyone else. Since you don't want things to get out of hand, you set up some rules for yourself. Firstly, you can give this person more than one cup of chocolates, but if you do, they must be numbered in order. For example, you may give this person cups 1, 2, and 3, but not cups 4, 5, and 7.

Additionally, you want to limit the total sweetness that you give out, so that this person doesn't get diabetes. Thus, after filling all the cups, you decide upon an inclusive upper limit $L$ ~L~ for the number of chocolates that you will give out, and now you want to know the maximum number of cups that this person can get.

Input Specification

The first line of input will contain two space-separated integers $N$ ~N~ and $T$ ~T~. Each of the next $T$ ~T~ lines will contain three space-separated integers $a$ ~a~, $b$ ~b~, and $c$ ~c~, representing a fill operation on cups $a$ ~a~ to $b$ ~b~ inclusive, adding $c$ ~c~ chocolates to each. Finally, the last line of input will contain the single integer $L$ ~L~.

Constraints

$1 \le N, T \le 10^6$ ~1 \le N, T \le 10^6~
$1 \le a \le b \le N$ ~1 \le a \le b \le N~
$1 \le c \le 10^3$ ~1 \le c \le 10^3~
$0 \le L \le 10^9$ ~0 \le L \le 10^9~

Output Specification

Output a single integer representing the maximum number of cups of chocolate that you could give to your "special someone".

Sample Input

Sample Output

Explanation

You have $6$ ~6~ cups, and perform $5$ ~5~ filling operations. After all of the fillings, the cups have $6$ ~6~, $7$ ~7~, $7$ ~7~, $8$ ~8~, $4$ ~4~, and $1$ ~1~ chocolates respectively. The possible ways to give them out are (with $1$ ~1~-indexed cups): $\{1\}$ ~\{1\}~, $\{2\}$ ~\{2\}~, $\{3\}$ ~\{3\}~, $\{4\}$ ~\{4\}~, $\{5\}$ ~\{5\}~, $\{6\}$ ~\{6\}~, $\{1, 2\}$ ~\{1, 2\}~, $\{4, 5\}$ ~\{4, 5\}~, $\{5, 6\}$ ~\{5, 6\}~, and $\{4, 5, 6\}$ ~\{4, 5, 6\}~, so thus, the maximum number of cups is $3$ ~3~.