现在是时候让 Hobanwoo 回到他魂牵梦绕的庆北大学了。然而有一个问题：从地球来到异世界很容易，但从异世界回到地球却很难。

在可以用二维坐标平面表示的宇宙中，除了异世界外，存在 $1$ 号到 $N$ 号共 $N$ 个行星。

对于 $1 \le i \le N$ 的每个 $i$，第 $i$ 号行星位于第一象限的 $(x_{i},\,y_{i})$，并拥有正整数对 $a_{i},\,b_{i}$。此外，$1$ 号到 $N$ 号行星的 $x_{i}$ 坐标构成一个递增序列。

Hobanwoo 最初位于异世界（即 $0$ 号行星，坐标为 $(0,\,0)$），他想要经过若干行星，最终到达拥有通往地球传送门的 $N$ 号行星。

当 Hobanwoo 当前位于 $s$ 号行星并想要前往 $e$ 号行星时，必须满足 $s \le e \le \min(N,s+M)$（其中 $M$ 为小于 $N$ 的正整数）。所需时间取决于从 $0$ 号到 $e$ 号行星构成的凸包：如果 $s$ 号行星在凸包上，则耗时 $a_{e}$；否则耗时 $b_{e}$。

请帮助 Hobanwoo 以最快速度到达 $N$ 号行星，以免上学迟到！

输入格式

第一行包含两个正整数 $N$ 和 $M$，中间用空格隔开。$(1 \le M < N \le 200\,000)$

接下来的 $N$ 行，每行包含 $1$ 号到 $N$ 号行星的 $x_{i},\,y_{i},\,a_{i},\,b_{i}$，中间用空格隔开。$(1 \le x_{i},\,y_{i},\,a_{i},\,b_{i} \le 10^{9})$

$x_{1},\,x_{2},\,x_{3}\ldots x_{N}$ 构成一个递增序列。

输出格式

输出 Hobanwoo 从异世界出发到达 $N$ 号行星所需的最短时间。

样例

输入 1

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

输出 1

101

输入 2

1 1
1 2 2 1

输出 2

2