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

문제

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

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

1ドル ≤ i ≤ 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 ≤ T ≤ 60,000円)$

각 테스트 케이스 별로 첫 번째 줄에 이세계를 제외한 행성의 개수인 $N$과 양의 정수 $M$이 공백을 두고 주어진다. $(1 ≤ M ≤ N ≤ 300,000円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 $x_{i},,円y_{i},,円a_{i},,円b_{i}$가 공백을 두고 주어진다. $(1 ≤ x_{i},,円y_{i},,円a_{i},,円b_{i} ≤ 10^{9})$

모든 테스트 케이스에 대하여 항상 $x_{1}<x_{2}<x_{3},円<\cdots<,円x_{N-1}<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()을 사용해야 합니다.