Recently you've discovered a new shooter. They say it has realistic game mechanics. Your character has a gun with magazine size equal to k and should exterminate n waves of monsters. The i -th wave consists of a_i monsters and happens from the l_i -th moment of time up to the r_i -th moments of time. All a_i monsters spawn at moment l_i and you have to exterminate all of them before the moment r_i ends (you can kill monsters right at moment r_i ). For every two consecutive waves, the second wave starts not earlier than the first wave ends (though the second wave can start at the same moment when the first wave ends) -- formally, the condition r_i <= l_{i + 1} holds. Take a look at the notes for the examples to understand the process better. You are confident in yours and your character's skills so you can assume that aiming and shooting are instant and you need exactly one bullet to kill one monster. But reloading takes exactly 1 unit of time. One of the realistic mechanics is a mechanic of reloading: when you reload you throw away the old magazine with all remaining bullets in it. That's why constant reloads may cost you excessive amounts of spent bullets. You've taken a liking to this mechanic so now you are wondering: what is the minimum possible number of bullets you need to spend (both used and thrown) to exterminate all waves. Note that you don't throw the remaining bullets away after eradicating all monsters, and you start with a full magazine. The first line contains two integers n and k ( 1 <= n <= 2000 ; 1 <= k <= 10^9 ) -- the number of waves and magazine size. The next n lines contain descriptions of waves. The i -th line contains three integers l_i , r_i and a_i ( 1 <= l_i <= r_i <= 10^9 ; 1 <= a_i <= 10^9 ) -- the period of time when the i -th wave happens and the number of monsters in it. It's guar