题目描述

Controlling traffic lights on crossing roads is one of the most essential applications of scheduling algorithms. Elaborating on those details will be a long story. In short, for this task, you will control the traffic lights to resolve a already-happened traffic jam.

The following figure shows a typical example of a crossing road in a Right-hand Traffic (RHT, meaning that drivers keep to the right side of the road). If we do not consider cases where drivers turn around, there are 12 directions: N->E, N->S, N->W, E->S, E->W, E->N, S->W, S->N, S->E, W->N, W->E and W->S. We have the situation here that there is already a traffic jam. The number of cars driving in the 12 directions are already known respectively. Each car needs 1 second to pass the crossing road to reach the destination. We assume there is no more traffic jam after they manage to drive through the crossing road. There will be no more cars entering this jam either.

Your task is to assign a appropriate traffic light for each second, so that the traffic jam is resolved (all the cars successfully pass the crossing roads) as quickly as possible. The assignment should also guarantee no potential collision between cars. The following figure show a valid example. Here is a bad case. It is illegal because there can be two collisions as marked in the figure, but we allow that two cars run into the S direction simultaneously and we do not penalize for this.

输入格式

输出格式

For each test case, output one number, which is the minumum number of seconds to resolve the traffic jam.

样例

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

1 
17

提示

牛客暑期多校训练营9 J题 SP9rk1e55转录