널빤지 건너기

해적 무리가 상선 한 척을 나포했다. 배가 너무 심하게 파손되어 항해할 수 없으므로, 상선의 화물을 전부 해적선으로 옮겨야 한다.

두 배 사이에는 널빤지 하나가 걸쳐져 있다. 해적들은 이 널빤지를 밟고 배 사이를 오갈 수 있지만, 널빤지는 한 번에 한 명만 버틸 수 있다.

모든 해적은 다음 네 단계를 반복한다.

각 해적에 대해 이 네 단계는 각각 정해진 시간이 걸리며, 그 시간은 항상 일정하다. 해적은 상선에서 더 가져올 물건이 없어질 때까지 이 과정을 반복한다.

널빤지 규칙:

널빤지가 사용 중일 때 도착한 해적은 자기 쪽에서 기다린다.
널빤지가 비었을 때 양쪽 모두에 기다리는 해적이 있으면, 상선 쪽(물건을 든 해적)이 먼저 건넌다.
각 쪽에서는 먼저 도착한 해적이 먼저 건너는 큐를 이룬다.
두 명 이상이 같은 쪽에 정확히 같은 순간 도착하면, 가장 느린 해적이 먼저 건넌다. 즉, 그 배의 화물칸까지 왕복하는 데 가장 오래 걸리는 해적이 먼저다.

첫 번째 해적이 널빤지를 건너기 시작한 순간부터 마지막 물건이 해적선으로 옮겨진 순간까지 걸리는 시간을 구하여라.

첫 줄에는 테스트 케이스의 수를 나타내는 정수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

두 정수 $N$과 $P$가 주어진다 ($1 \le N \le 100000$, $1 \le P \le 1000$). 각각 상선에 있는 물건의 수와 해적의 수이다.
이어서 $P$개의 줄이 주어진다. $i$번째 줄에는 네 정수 $t_1, t_2, t_3, t_4$가 주어진다 ($1 \le t_i \le 1000$). 해적 $i$가 위 네 단계를 수행하는 데 각각 걸리는 시간(초)이다.

처음에 모든 해적은 입력에 주어진 순서대로 해적선 쪽 널빤지 앞에 줄을 서 있으며, 가장 먼저 나온 해적이 가장 먼저 건넌다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 첫 번째 해적이 널빤지를 건너기 시작한 순간부터 마지막 물건이 해적선으로 옮겨진 순간(마지막으로 되돌아오는 건넘이 끝나는 순간)까지 걸린 시간을 초 단위로 나타낸 값이다.