MUV LUV ALTERNATIVE

In order to cover the Tactical Armored Squadron withdrawing, the IJN Combined Fleet’s 2nd Squadron is attracting attacks from Lux. After a while, the fleet is heavily damaged and some ships have been on fire. The soldiers on one fired ship are trying escaping from the cabin and reaching the board.
The cabin can be abstracted into a grid of n×m, where rows are numbered 1, 2, · · · , n from bottom to top and columns are numbered 1, 2, · · · , m from left to right. The cabin is divided into 3 seated zones by 2 vertical corridors of width 1, where the left zone is of width l1, the middle zone is of width l2 and
the right zone is of width l3. Also, for the two corridors, one is between the left zone and the middle zone and the other one is between the middle zone and the right zone so that l1 + l2 + l3 + 2 = m always holds. Let’s use (x, y) to denote the location of the cell in the x-th row and the y-th column.
Below the two corridors are the left exit and the right exit, which can be considered to be positioned at (0, l1 + 1),(0, l1 + l2 + 2) respectively. Following is the illustration when n = 4, l1 = l2 = l3 = 2.
There are k soldiers inside the cabin, each soldier is in a unique cell (xi , yi) in one of the three seated zones initially. A soldier in seated zones can only move leftward or rightward, while one in corridors can move not only leftward or rightward, but also upward or downward. And one soldier can stay still or move to an adjacent cell in one of the allowed directions according to its current position at every moment. Two cells are adjacent if and only if they share an edge. Each cell mustn’t contain more than one soldier after each moment’s movement.
For maintaining the order of escape, the soldiers who are initially in the left zone can only go to the left exit, while ones who are initially in the right zone can only go to the right exit. For ones who are initially in the middle zone, they can go to either the left exit or the right exit.
You want to know the minimum possible time that all the soldiers have reached one of the two exits.

The first line contains five positive integers n, l1, l2, l3, k (1 ≤ k ≤ 100 000, 1 ≤ n, l1, l2, l3 ≤ 109), denoting the number of rows, the three widths of the left zone, the middle zone, the right zone, and the number of soldiers respectively.
Next k lines each contains three positive integers ai , xi , yi (ai ∈ {1, 2, 3}, 1 ≤ xi ≤ n, 1 ≤ yi ≤ l1 + l2 + l3 + 2, yi = l1 + 1, yi = l1 + l2 + 2), denoting the initial position of a soldier, where ai denotes the zone index and xi , yi denotes the row index and the column index respectively.
It is guaranteed that input k positions are pairwise distinct and that (xi , yi) is indeed in the zone ai.

Output a single line containing a positive integer, denoting the minimum possible time.

4 2 2 2 3
1 2 1
1 2 2
2 2 4

4

One possible scheme is as follows, where “S”, “E” denote soldiers and exits respectively:
1. Moment 0: Initial status
2. Moment 1: three soldiers move to (2, 2),(2, 3),(2, 5) respectively.
3. Moment 2: three soldiers move to (2, 3),(1, 3),(2, 6) respectively.
4. Moment 3: three soldiers move to (1, 3),(0, 3),(1, 6) respectively, where the second soldier has reached the left exit.
5. Moment 4: the remaining two soldiers move to (0, 3),(0, 6) respectively, where the three soldiers have all reached the exits. So the cost time is 4 during the escape.

642ccpcQHD