It is now time for Hobanwoo to return to the beloved Kyungpook National University. However, there is one problem: while it is easy to come from Earth to the otherworld, returning from the otherworld to Earth is difficult.

In the universe, which can be represented as a 2D coordinate plane, there are $N$ planets numbered from $1$ to $N$, excluding the otherworld.

For each $i$ such that $1 \le i \le N$, planet $i$ is located at $(x_{i}, y_{i})$ in the first quadrant and has a pair of positive integers $a_{i}$ and $b_{i}$. The $x$-coordinates $x_{i}$ of the planets from $1$ to $N$ form an increasing sequence.

Hobanwoo starts at the otherworld, which is planet $0$ at $(0, 0)$, and wants to reach planet $N$, where the portal to return to Earth is located, by passing through several planets.

When Hobanwoo is currently at planet $s$ and wants to go to planet $e$, he can do so if and only if $s < e \le \min(N, s+M)$ for a given positive integer $M < N$. The time taken is $a_{e}$ if planet $s$ is part of the convex hull of the set of planets $\{0, 1, \dots, e\}$, and $b_{e}$ otherwise.

Help Hobanwoo reach planet $N$ as quickly as possible so he does not arrive late for school!

Input

The first line contains two positive integers $N$ and $M$, separated by a space, where $1 \le M < N \le 200\,000$.

The next $N$ lines each contain $x_{i}, y_{i}, a_{i}, b_{i}$ for planets $1$ through $N$, separated by spaces, where $1 \le x_{i}, y_{i}, a_{i}, b_{i} \le 10^{9}$.

The sequence $x_{1}, x_{2}, x_{3}, \dots, x_{N}$ is strictly increasing.

Output

Output the minimum time required for Hobanwoo to travel from the otherworld to planet $N$.

Examples

Input 1

4 2
102180138 230636159 100 100
261562641 590386782 100 100
300000000 100000000 100 100
408720552 922544636 100 1

Output 1

101

Input 2

1 1
1 2 2 1

Output 2

2