이제 호반우가 그립고 그리운 경북대학교로 돌아가야 할 때가 왔다. 그러나 문제가 하나 있었으니, 지구에서 이세계로 오기는 쉬워도 이세계에서 지구로 돌아가는 건 어렵다는 것이다.

2차원 좌표평면으로 나타낼 수 있는 우주에는 이세계를 제외한 $1$번부터 $N$번까지 $N$개의 행성이 존재한다.

$1 \le i \le N$인 $i$에 대해 $i$번 행성은 1사분면 위에 위치한 $(x_{i},\,y_{i})$에 있고 양의 정수 쌍 $a_{i},\,b_{i}$를 가지며 $1$번부터 $N$번까지 행성들의 $x_{i}$들은 증가 수열을 이룬다.

호반우는 처음에 이세계이자 $0$번 행성인 $(0,\,0)$에 있으며 여러 행성을 거쳐 지구로 돌아가는 차원문이 있는 $N$번 행성에 가려고 한다.

현재 호반우가 $s$번 행성에 있고 $e$번 행성에 가려고 할 때 $N$미만의 양의 정수 $M$에 대해 $s \le e \le \min(N,s+M)$을 만족해야 갈 수 있으며 걸리는 시간은 0번부터 e번까지의 행성들로 볼록껍질을 만들었을 때 s번 행성이 볼록껍질을 이루고 있다면 $a_{e}$의 시간이 걸리고 그렇지 않다면 $b_{e}$의 시간이 걸린다.

호반우가 학교에 지각하지 않기 위해 $N$번 행성까지 빠르게 갈 수 있도록 도와주자!

Input

첫 번째 줄에 양의 정수 $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}$은 증가 수열을 이룬다.

Output

호반우가 이세계에서 출발해 $N$번 행성에 도착하기까지 걸리는 시간의 최솟값을 출력한다.

Examples

Input 1

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
1 2 2 1

Output 2

2