Why Hobanwoo Was Late for School 8

Now Hobanwoo wants to return to the beloved Kyungpook National University. There is one problem, though. Getting from Earth to the otherworld is easy, but getting back from the otherworld to Earth is hard.

In a universe that can be drawn on a two-dimensional coordinate plane, there are $N$ planets besides the otherworld. Sorted by increasing $x$ value, they are called planet 1, planet 2, ..., planet $N$.

For each $i$ with $1 \le i \le N$, planet $i$ is located at the integer coordinate $(x_i, y_i)$ in the first quadrant and has positive integers $a_i$ and $b_i$.

At first, Hobanwoo is at $(0, 0)$, which is the otherworld and the position of planet 0. Hobanwoo wants to reach planet $N$, where a dimensional gate back to Earth is located, by passing through several planets.

Hobanwoo can pass over $M$ planets in a single move. More precisely, when Hobanwoo is at planet $s$ and wants to move to planet $e$, it must hold that $s \le e \le s+M$. The travel time is $a_e$ if planet $s$ lies on the boundary of the smallest convex polygon that contains all planets from planet 0 to planet $e$. Otherwise, the travel time is $b_e$. A straight line counts as a convex polygon.

Help Hobanwoo arrive at planet $N$ from the otherworld quickly so that he is not late for school!

The first line contains the number of test cases $T$. ($1 \le T \le 60\,000$)

Each test case begins with a line containing $N$ and $M$, separated by a space. ($1 \le M \le N \le 300\,000$)

From the second line onward, the next $N$ lines each contain $x_i$, $y_i$, $a_i$, and $b_i$, separated by spaces. ($1 \le x_i, y_i, a_i, b_i \le 10^9$)

For every test case, $x_1 < x_2 < \cdots < x_N$ always holds.

The sum of $N$ over all test cases does not exceed $300\,000$.

For each test case, print the minimum time it takes for Hobanwoo to start from the otherworld and reach planet $N$.

Input and output are large, so fast I/O is recommended. Fast I/O for common languages is described below.

• C++: If you use cin and cout, you must call cin.tie(nullptr); ios::sync_with_stdio(false); once before any I/O. To start a new line, use '\n' instead of endl.
• Java: You must use BufferedReader and BufferedWriter.
• Python3, PyPy3: Use sys.stdin.readline().rstrip() instead of input().