호반우가 학교에 지각한 이유 8

이제 호반우는 그리운 경북대학교로 돌아가려고 한다. 그러나 문제가 하나 있다. 지구에서 이세계로 오는 것은 쉬워도, 이세계에서 지구로 돌아가는 것은 어렵다.

2차원 좌표평면으로 나타낼 수 있는 우주에는 이세계를 제외한 $N$개의 행성이 있다. $x$값이 작은 순서대로 1번 행성, 2번 행성, ..., $N$번 행성이라고 부른다.

$1 \le i \le N$인 $i$에 대해 $i$번 행성은 1사분면 위에 있는 정수 좌표 $(x_i, y_i)$에 있고, 양의 정수 $a_i$, $b_i$를 가진다.

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

호반우는 한 번의 이동에 $M$개의 행성을 지나칠 수 있다. 정확히는, 호반우가 $s$번 행성에 있을 때 $e$번 행성으로 이동하려면 $s \le e \le s+M$을 만족해야 한다. 이때 이동 시간은 0번부터 $e$번까지의 행성들을 모두 포함하는 가장 작은 볼록 다각형을 만들었을 때, $s$번 행성이 볼록 다각형 경계에 위치하면 $a_e$, 그렇지 않으면 $b_e$이다. 직선도 볼록 다각형으로 본다.

이세계에서 $N$번 행성까지 빠르게 도착해서 호반우가 학교에 지각하지 않도록 도와주자!

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 60\,000$)

각 테스트 케이스의 첫 번째 줄에는 공백을 두고 $N$과 $M$이 주어진다. ($1 \le M \le N \le 300\,000$)

두 번째 줄부터 $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 < \cdots < x_N$을 만족한다.

모든 테스트 케이스의 $N$의 합은 $300\,000$을 넘지 않는다.

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

입출력의 양이 많으므로 빠른 입출력을 사용하는 것을 권장한다. 언어별 빠른 입출력은 아래를 참고한다.

• C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 한다. 줄 바꿈할 때는 endl 대신 '\n'을 사용해야 한다.
• Java: BufferedReader와 BufferedWriter를 사용해야 한다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 한다.