MUV LUV ALTERNATIVE

为了掩护战术机部队撤退，舰队承担了吸引BETA的任务，并因此遭受了光线级BETA的猛烈攻击。起火的军舰上，军人需要从船舱逃到甲板上。

船舱可以看做一个$n$行，$m$列的矩形。船舱分为$3$个区域，宽度分别为$l_1,l_2,l_3$。每$2$个相邻的区域的交界处有一条过道。

位于座位区域的军人只能够横向移动，位于过道区域的军人可以向四个方向移动，每个军人可以在每个时刻移动恰好$1$单位距离或保持不动，任意位置同时至多只能有$1$名军人。为了保证有序地逃生，区域$1$的军人只会从左侧的出口逃生，区域$3$的军人只会从右侧的出口逃生，区域$2$的军人可以从任意一个出口逃生。

下图是一个$n=4,l_1=2,l_2=2,l_3=2$的例子。

请问至少经过多长时间，所有的军人才能逃到甲板上。

第$1$行$5$个整数$n,l_1,l_2,l_3,k$，其中$n,l_1,l_2,l_3$的含义如题目描述，$k$表示军人的数量。

接下来$k$行，每行$3$个整数$a_i,x_i,y_i$，表示初始时有一个位于区域$a_i$的军人，位于$x_i$行$y_i$列。

保证初始时过道上不会有军人。

保证初始时不会有两个军人在同一个位置。

$1\le n,l_1,l_2,l_3 \le 10^9$

$1\le k \le 10^5$

$1\le a_i \le 3$

$1\le x_i \le n$

$1\le y_i \le l_1+l_2+l_3+2$

输出$1$个整数表示最少逃生时间。

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

4

642ccpcQHD

一个最优的移动方案如下：

在0时间，3名军人分别位于 (2,1) (2,2) (2,4)

在1时间，3名军人分别移动到(2,2) (2,3) (2,5)

在2时间，3名军人分别移动到(2,3) (1,3) (2,6)

在3时间，3名军人分别移动到(1,3) (0,3) (1,6)，第二名军人成功逃出船舱。

在4时间，剩下两名军人移动到(0,3) (0,6)，逃出船舱。