410671: GYM104072 I Mortgages

Recently, Max decided to become a house flipper. Because this is a hard business to start, he went to the bank to inquire about their offers.

The bank has $$$N$$$ house offers defined by the following attributes:

• $$$t_i$$$ - the exact moment in time the offer is available (i.e. it is available only at that time). It is guaranteed that these values are distinct, and that the offers are given in a non-descending order by their availability time $$$t_i$$$.
• $$$p_i$$$ - the initial price of the house
• $$$d_i$$$ - the down deposit needed in order to be able to take the offer
• $$$r_i$$$ - the monthly rate which Max will need to pay to the bank
• $$$m_i$$$ - the number of months Max will need to pay the rate
• $$$inc_i$$$ - the monthly increase of the house price

This means that $$$X$$$ months after Max buys a house, the house will be valued at $$$p_i + X*inc_i$$$ dollars and he will have payed the bank $$$d_i + min(X, m_i)*r_i$$$ dollars. Max starts with an infinite amount of money (so he can put any deposit needed), and a final moment $$$T$$$ when he wants to end all business. Also, he is restricted to only be able to own at most one house at a time. This means that he will be able to accept a bank offer only if he does not own any houses at that time (he can also decide to skip some of the offers).

At a moment in time, Max can decide to sell his current house (if he owns one). When a house is sold, Max will need to pay all the remaining monthly rates to the bank, so that all $$$m_i$$$ are payed. This action happens instantaneously.

Help Max find what is the maximum profit he can make using the bank offers. The profit is described as the total money he has made selling the houses subtracted by the total money used to buy the houses.

The first line of input contains $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$T$$$ ($$$1 \leq T \leq 10^9$$$), denoting the number of houses and the end time.

Each of the following $$$N$$$ lines contains $$$6$$$ positive integers describing the houses:

• $$$t_i$$$ ($$$1 \leq t_i < T$$$)
• $$$p_i$$$ ($$$1 \leq p_i \leq 10^6$$$)
• $$$d_i$$$ ($$$1 \leq d_i \leq p_i$$$)
• $$$r_i$$$ ($$$1 \leq r_i \leq 10^6$$$)
• $$$m_i$$$ ($$$1 \leq m_i \leq 10^6$$$)
• $$$inc_i$$$ ($$$1 \leq inc_i \leq 10^6$$$)

On a single line, print the maximum profit Max can make in the time given.

9 50
1 1 1 2 1 4
10 1 1 2 2 5
12 4 1 2 5 2
21 5 4 5 1 2
22 3 2 5 5 2
28 3 2 5 1 1
31 1 1 3 1 2
39 3 3 2 1 2
49 4 1 3 2 3

230

4 55
2 3 2 3 1 1
3 2 2 3 1 5
5 1 1 5 3 3
48 2 1 5 5 5

257

10 33
1 2 1 4 4 3
2 1 1 3 4 5
5 2 1 2 4 1
8 4 4 1 4 1
13 3 2 5 2 3
16 3 3 1 2 1
19 2 2 3 3 4
21 2 2 1 5 4
24 1 1 5 2 5
26 5 3 4 4 5

143