## RGPC '18 P3 - Chocolate Day

View as PDF

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 cups numbered in order from to , and you fill them times. More specifically, for each filling, you add chocolates to all the cups between cup and cup 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 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 and . Each of the next lines will contain three space-separated integers , , and , representing a fill operation on cups to inclusive, adding chocolates to each. Finally, the last line of input will contain the single integer .

#### Output Specification

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

#### Sample Input

6 5
1 4 4
1 3 2
4 5 4
2 3 1
6 6 1
13

#### Sample Output

3

#### Explanation

You have cups, and perform filling operations. After all of the fillings, the cups have , , , , , and chocolates respectively. The possible ways to give them out are (with -indexed cups): , , , , , , , , , and , so thus, the maximum number of cups is .