题目描述

在信号处理中，人们有时会对一个给定表达式的最大值感兴趣。这个表达式只含有按位与（AND）和按位或（OR）运算，变量都为整数且有一定的取值范围。请你编写程序，求出一个给定表达式的最大值。为了简化题目，这里只考虑一种特殊的表达式，它有若干个由 AND 连接的子表达式构成，而每个子表达式内只含有 OR 运算。这样，一个表达式可以由它的子表达式数量和每个表达式内变量的个数唯一确定。

例如，$(3,\ 1,\ 2,\ 2)$ 表示的表达式为 $E=(v_1\ \texttt{OR}\ v_2\ \texttt{OR}\ v_3)\ \texttt{AND}\ (v_4)\ \texttt{AND}\ (v_5\ \texttt{OR}\ v_6)\ \texttt{AND}\ (v_7\ \texttt{OR}\ v_8)$。

输入格式

第一行为两个整数 $N$ 和 $P$，其中 $N$ 为变量的个数（$1\leq N\leq 100$），$P$ 为子表达式的个数（$1\leq P\leq N$）。

第二行为 $P$ 个整数 $K_1,\ K_2,\ \cdots,\ K_P$，其中 $K_i$ 表示第 $i$ 个子表达式的变量个数（$K_i\geq 1$，$\sum_{i=1}^P K_i=N$）。

接下来 $N$ 行，每行两个整数 $A_j$ 和 $B_j$，表示变量 $v_j$ 的取值范围为 $[A_j,\ B_j]$（$0\leq A_j\leq B_j\leq 2\times 10^9$）。

输出格式

一个整数，表示表达式的最大值。

8 4
3 1 2 2
2 4
1 4
0 0
1 7
1 4
1 2
3 4
2 3

6