题目描述
小 $\gamma$ 在看朋友玩游戏。
有 $t$ 个困难的关卡需要玩家依次通过。为了帮助玩家通关，游戏提供了 $n$ 瓶药水，第 $i$ 瓶药水会在到达第 $a_i$ 个关卡前获得，在第 $b_i$ 个关卡后过期，能让游戏角色的能力值在下一个关卡中提升至 $v_i$，另有额外的神秘属性 $c_i$。每个关卡前玩家可以选择其中一瓶药水使用。由于小 $\gamma$ 的朋友水平很菜，你需要保证每个关卡前都使用药水，且第 $i$ 个关卡时玩家的能力值至少提升至 $h_i$。由于药水量很大，每次使用并不会用完，你可以在过期前重复使用。
小 $\gamma$ 与他的朋友发现在一段时间内使用神秘属性相差过大的药水会导致药力相冲，对游戏角色的长期培养不利，但他们并不清楚游戏的一些具体数值，因此他们希望在通过这 $t$ 个关卡的基础上保证过程中使用的神秘属性相差最大的两瓶药的神秘属性相差值最小。
小 $\gamma$ 已经通过人类智慧迅速地得出了一个方案，因此为了方便起见，你只需要告诉他这个最小值进行验算即可。
输入格式
第 $1$ 行 $2$ 个整数 $\mathtt{t\ n}$。
第 $2$ 行至第 $n + 1$ 行，第 $i + 1$ 行 $4$ 个整数 $\mathtt{a_i\ b_i\ c_i\ v_i}$。
第 $n + 2$ 行 $t$ 个整数 $\mathtt{h_1\ h_2\ \dots\ h_t}$。
输出格式
$1$ 行 $1$ 个整数 $\mathtt{d}$，表示满足条件的方案中使用的药水的神秘属性最大差值的最小值，如果没有满足条件的方案，则规定 $d = -1$。
样例一
input
5 8 2 5 100 10 1 4 6 2 2 4 1 5 1 2 3 5 4 5 5 6 4 5 2 4 1 2 5 3 1 4 200 10 5 3 2 4 5
output
3
explanation
在第一个关卡前，获得了第 $2, 4, 7, 8$ 瓶药水。
第一个关卡需要能力值 $5$，符合的药水有属性为 $3$ 的第 $4$ 瓶与属性为 $200$ 的第 $8$ 瓶。可以选择第 $4$ 瓶使用。
在第二个关卡前，获得了第 $1, 3$ 瓶药水。
第二个关卡需要能力值 $3$，符合的药水有属性为 $100$ 的第 $1$ 瓶，属性为 $1$ 的第 $3$ 瓶，属性为 $3$ 的第 $4$ 瓶，属性为 $5$ 的第 $7$ 瓶与属性为 $200$ 的第 $8$ 瓶。可以仍选择第 $4$ 瓶使用。
在第三个关卡前，第 $4, 7$ 瓶药水过期。
第三个关卡需要能力值 $2$，符合的药水有属性为 $100$ 的第 $1$ 瓶，属性为 $6$ 的第 $2$ 瓶，属性为 $1$ 的第 $3$ 瓶与属性为 $200$ 的第 $8$ 瓶。可以选择第 $2$ 瓶使用。
在第四个关卡前，获得了第 $5, 6$ 瓶药水。
第四个关卡需要能力值 $4$，符合的药水有属性为 $100$ 的第 $1$ 瓶，属性为 $1$ 的第 $3$ 瓶，属性为 $5$ 的第 $5$ 瓶，属性为 $2$ 的第 $6$ 瓶与属性为 $200$ 的第 $8$ 瓶。可以选择第 $5$ 瓶使用。
在第五个关卡前，第 $2, 3, 8$ 瓶药水过期。
第五个关卡需要能力值 $5$，符合的药水有属性为 $100$ 的第 $1$ 瓶与属性为 $5$ 的第 $5$ 瓶。可以选择第 $5$ 瓶使用。
以上给出的方案使用了第 $2, 4, 5$ 瓶药水使用，神秘属性的最大差值为 $3$，可以证明这是符合条件的最小的最大差值。注意方案不唯一，在该样例中存在其它方案同样能达到这个最小值。
样例二
input
2 1 1 1 1 1 1 1
output
-1
explanation
注意到关卡二前没有药水可以使用，不存在合法方案，我们规定了 $d = -1$。
样例三
input
10 10 1 6 671936242 42405117 9 10 515984733 846156198 5 6 733821371 125341798 3 6 752975928 920346417 5 5 997219535 657906650 4 9 644307583 871090710 5 10 827293402 283686108 1 5 211376630 373884341 2 3 825647949 768225427 2 9 558922034 796865891 11122194 289469209 919054766 911821750 749480037 884093255 161270396 162695531 821082659 21449452
output
182985819
限制与约定
本题采用子任务形式。
对于 $5\%$ 的数据，保证 $1 \leqslant t, n \leqslant 7$。
对于 $10\%$ 的数据，保证 $1 \leqslant t \leqslant 7, 1 \leqslant n \leqslant 14$。
对于 $15\%$ 的数据，保证 $1 \leqslant t, n \leqslant 14$。
对于 $20\%$ 的数据，保证 $1 \leqslant t, n \leqslant 20$。
对于 $40\%$ 的数据，保证 $1 \leqslant t, n \leqslant 10^3$。
对于 $50\%$ 的数据，保证 $1 \leqslant t, n \leqslant 10^5$。
对于另外 $10\%$ 的数据，保证 $a_i = b_i$。
对于另外 $10\%$ 的数据，保证 $h_i = 1$。
对于含以上共 $80\%$ 数据，保证 $1 \leqslant t, n \leqslant 5 \times 10^5$。
对于 $100\%$ 的数据，保证 $1 \leqslant t, n \leqslant 10^6, 1 \leqslant a_i\le b_i \le t,1\le c_i,v_i,h_i\le 10^9$