2015
05-23

# Walking the Plank

A bunch of pirates have successfully conquered a commercial vessel. The ship itself is too badly damaged, so the entire shipload needs to be transferred to the pirate ship.
The pirates have anchored a plank to both ships, which the pirates can use to go from one ship to the other, but it can only support one pirate at a time.
Each pirate executes the following routine:
1. Walk across the plank from the pirate ship to the commercial ship
2. Pick up an item from the cargo hold and return to the plank
3. Cross the plank back to the pirate ship with the item
4. Put the item in the cargo hold and return to the plank
Each of these four steps takes a given amount of time for each pirate. Every pirate will repeat these steps until the number of pirates on the commercial ship equals the number of items there (i.e. there’s nothing more for the pirate to collect).
If a pirate gets to the plank and it’s in use by another pirate, he will wait at his side of the plank. When the plank is vacated and there are pirates on both sides of the plank, the pirates on the side of the commercial vessel (carrying some item) will get to go first. At both sides of the plank, the pirates queue up, i.e. the first one to get there will be the first one to cross. Should two or more pirates arrive at the same side of the plank at the exact same time, the pirate who was slowest (i.e. the one who has taken the most time to and from the cargo hold on this ship) gets to go first.Can you determine how long it takes before the last pirate has crossed the plank with the last item?

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with two integers N and P, satisfying 1 <= N <= 100,000 and 1 <= P <= 1,000: the number of items on the commercial vessel and the number of pirates, respectively.
2.P lines, each with 4 integers t1 through t4, satisfying 1 <= ti <= 1,000: the time in seconds it takes this pirate to complete each step (as listed above).
At the start, all pirates are queued up at the plank on the pirate ship in the order given in the input (the first pirate is the first to cross over).

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
1.One line with two integers N and P, satisfying 1 <= N <= 100,000 and 1 <= P <= 1,000: the number of items on the commercial vessel and the number of pirates, respectively.
2.P lines, each with 4 integers t1 through t4, satisfying 1 <= ti <= 1,000: the time in seconds it takes this pirate to complete each step (as listed above).
At the start, all pirates are queued up at the plank on the pirate ship in the order given in the input (the first pirate is the first to cross over).

3
3 3
10 3 10 3
10 3 10 3
10 3 10 3
3 2
10 10 10 10
1 9 1 8
3 2
3 2 3 6
4 2 5 5

63
50
24

1. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

2. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

3. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

4. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

5. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

6. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

7. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

8. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

9. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

10. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

11. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

12. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

13. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

14. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

15. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗

16. 小哥 不要发这种自我意淫的内容了好么 没有更新的内容就空着不要发 要发也不要发这种低级的内容 反叛大人就是深蓝一部分特征吗 我去 你当现在的父母都是60 50后的吗 80后的父母和孩子相处你知道是怎么样的吗