F. Far island treasure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On a remote island, adventurers gather in search of a legendary treasure hidden deep within a mysterious jungle. The path to the treasure is full of challenges, and one of the most intriguing is the "Operation Challenge."

In this challenge, adventurers are given an initial array of size $$$10^9$$$, filled with virtual treasures (initially all zeros). They must then perform a series of $$$N$$$ operations on the array. Each operation is described by three numbers: $$$l$$$, $$$r$$$, and $$$x$$$, indicating that $$$x$$$ should be added to each element in the range from position $$$l$$$ to position $$$r$$$ (inclusive).

Once all operations have been completed, the next step of the challenge is to find the maximum treasure that can be obtained by adding all the elements of a subarray of size $$$K$$$. Adventurers must use their wits and skills to solve this puzzle and determine what the maximum treasure they can obtain is.

Given the array after all operations and the value of $$$K$$$, your task is to help adventurers find the maximum sum of the elements that can be obtained by taking a subarray of size $$$K$$$.

Input

The input consists of several lines:

- The first line contains two integers, $$$N$$$ $$$(1 \leq N \leq 10^5)$$$ and $$$K$$$ $$$(1 \leq K \leq 10^9)$$$, representing the number of operations and the size of the subarray adventurers should consider, respectively.

- The following $$$N$$$ lines each contain three integers: $$$l$$$, $$$r$$$, and $$$x$$$ $$$(1 \leq l \leq r \leq 10^9, 1 \leq x \leq 1000)$$$, representing an operation on the array. Each operation indicates that $$$x$$$ should be added to each element in the range from position $$$l$$$ to position $$$r$$$ (inclusive).

Output

You should print a single integer, representing the maximum sum of the elements that can be obtained by taking a subarray of size $$$K$$$ after all operations have been performed.

Examples
Input
4 3
1 10 1
2 8 2
4 6 3
5 5 4
Output
22
Input
4 1
1 10 1
2 8 2
4 6 3
5 5 4
Output
10
Input
4 100
1 10 1
2 8 2
4 6 3
5 5 4
Output
37