题目描述

小马利亚北部防护林一共有 $m$ 棵高度不同的树，第 $i$ 个树的高度为 $h_i$。暮光闪闪一共有 $n$ 个朋友。每个朋友心中都有自己至少想要认领的树的数量 $c_i$。值得注意的是：有些小马只想正好认领某个数目的树。每只小马有自己的身高，第 $i$ 只小马的身高为 $x_i$。每个小马有一个控制范围 $p_i$，一头小马能够认领一棵树当且仅当树的高度在区间 $[\max(0,x_i-p_i),x_i+p_i]$ 内。若一棵树被一匹小马认领，由于大家是朋友，所有控制范围中包含这棵树的小马应当一同认领。现在塞拉斯缇娅公主非常担心自己的防护林的树木的数量，她想知道她的防护林至少有多少棵树能被认领。

输入格式

第一行两个整数 $n,m$ 表示暮光闪闪的伙伴数和防护林的树的数量。
第二行六个整数，表示后面的限制条件是否满足，$0$ 为不满足，$1$ 为满足，这是为了方便判定部分分。
接下来一行 $m$ 个整数表示树的高度 $h_i$。
接下来 $n$ 行，每行四个整数 $k_i,x_i,p_i,c_i$，第一个数是一个判定，第二个表示小马的身高，第三个表示小马的控制范围，当第一个数为 $0$ 时，表示当前这匹小马想要正好认领 $c_i$ 棵树，第一个数为 $1$ 时，表示当前这匹小马想要认领至少 $c_i$ 棵树。

输出格式

输出一行一个整数, 表示最少有多少棵树被认领。如果没有办法满足每个小马认领的需求，则输出 No ANSWER。

5 7
0 0 0 0 0 0
5 9 18 14 6 30 10000000
0 13 12345678 4
1 10 5 2
1 10 4 2
1 14 1 1
1 30 0 1

4

数据范围与提示

对于所有数据，有$1 \leq n \leq 20000$，$1\le m\le 50000$，$1 \leq x_i,p_i,h_i \leq 10 ^ 9$，$k \in \{0,1\}$，$0 \leq c_i \leq 2\times 10 ^ 9$。保证 $h_i$ 各不相同，数据随机生成。

题目给出六类部分分限制，具体如下：

限制一：对于任意小马 $i\in[1,n],p_i=0$。

限制二：对于任意小马 $i\in(1,n]$，有 $c_i-c_{i-1}=0$。

限制三：对于任意小马 $i\in[1,n]$，令它的控制范围为 $I_i$，则在 $(1,n]$ 上，$I_i\cap I_{i-1}\cap \mathbb{Z}$ 最多只有 $1$ 个元素。

限制四：对于任意小马 $i\in[1,n]$，控制范围中含有的树的数量相同。

限制五：对于任意小马 $i\in[1,n]$，有 $k_i\neq 0$。

限制六：令 $T$ 表示大树高度集，那么 $1\in T$，当 $a\in T$ 且 $a<m$ 时，$a+1\in T$。