Walking the Plank

A band of pirates has captured a merchant ship. The ship is too badly damaged to sail, so its entire cargo must be moved to the pirate ship.

A single plank is laid between the two ships. Any pirate can cross it to move from one ship to the other, but the plank can support only one pirate at a time.

Every pirate repeats the following four steps:

1. Cross the plank from the pirate ship to the merchant ship.
2. Fetch one item from the cargo hold and walk back to the plank.
3. Cross the plank back to the pirate ship, carrying the item.
4. Store the item in the cargo hold and walk back to the plank.

For each pirate, every one of these four steps always takes a fixed amount of time. A pirate keeps repeating the routine until there is nothing left to collect on the merchant ship.

Plank rules:

• If a pirate reaches the plank while it is in use, that pirate waits on its own side.
• When the plank becomes free and pirates are waiting on both sides, the pirate on the merchant-ship side (carrying an item) goes first.
• On each side the waiting pirates form a queue: the first to arrive is the first to cross.
• If two or more pirates reach the same side at exactly the same instant, the slowest one goes first — that is, the one whose round trip to and from that ship's cargo hold takes the most time.

How much time passes between the moment the first pirate starts crossing the plank and the moment the last item has been carried across to the pirate ship?

The first line contains one integer: the number of test cases. Each test case has the following format:

• One line with two integers $N$ and $P$ ($1 \le N \le 100000$, $1 \le P \le 1000$): the number of items on the merchant ship and the number of pirates.
• $P$ lines follow. The $i$-th line contains four integers $t_1, t_2, t_3, t_4$ ($1 \le t_i \le 1000$): the time in seconds pirate $i$ needs for each of the four steps above, in order.

At the start, all pirates are queued at the plank on the pirate ship in the order given in the input; the first pirate listed is the first to cross.

For each test case, print one line with a single integer: the number of seconds between the moment the first pirate begins crossing the plank and the moment the last item is carried across to the pirate ship (that is, when the final return crossing completes).