P7637 [BalticOI 2006] BITWISE EXPRESSIONS (Day 1)

在信号处理中，当变量是在一定范围内的整数时，人们有时会对包含按位 AND 和 OR 运算符的某个表达式的最大值感兴趣。你要编写一个程序，以这样的表达式和每个变量的范围作为输入，并确定表达式可以接受的最大值。

为简单起见，该表达式具有特定的形式，即由按位 AND 操作符（表示 $\& $）分隔的圆括号内的若干子表达式。每个子表达式由一个或多个变量组成，变量之间用按位 OR 操作符（表示为 $|$ ）分隔。使用这种约定，可以通过给出子表达式的数量以及每个子表达式中变量的数量来完全指定表达式。变量只是根据它们在表达式中的出现情况进行编号。 举例，如果子表达式的个数为 $4$，并且每个子表达式中的变量个数为 $3$，$1$，$2$，$2$，则表达式为: $$E=(v_1|v_2|v_3) \& (v_4) \& (v_5|v_6) \& (v_7|v_8)$$ 按位操作符是用普通的方式定义的。例如，要执行 $21 \& 6$ 的运算，我们首先写下数字（操作数）的二进制形式：$10101$ 和 $110$（因为 $21=2^4+2^2+2^0$ 和 $6=2^2+2^1$）。结果中的每个二进制数字现在都取决于操作数中对应的数字:如果两个操作数中都是 $1$，那么结果数字就是 $1$，否则就是 $0$。如下图最左边所示，结果值为 $4$。如果我们想计算 $21| 6$，其过程是相同的，唯一不同的是，如果对应的数字在任何一个操作数中都是 $1$，则结果是 $1$，因此只有在两个操作数中都是 $0$ 的情况下，结果才会是 $0$。如下图中央所示，结果是 $23$。推广到两个以上操作数是很简单的。下面最右边的例子说明了 $30 \& 11 \& 7=2$。 

第一行给出两个正整数 $N$ 和 $P$。第二行给出 $P$ 个正整数（$K_1,K_2, \cdots ,K_P$），其中 $K_i$ 为第 $i$ 个子表达式中的变量个数。$K_i$ 都大于等于 $1$，并且它们的和等于 $N$。下面 $N$ 行中每一行包含两个整数 $A_j$ 和 $B_j$，根据 $A_j \le v_j \le B_j$ 指定表达式中第 $j$ 个变量的取值范围。

一行，包含一个整数：表达式可以接受的最大值。

#### 数据规模与约定 对于 $100 \% $ 的数据，$1 \le N \le 100$，$1 \le P \le N$，$0 \le A_j \le B_j \le 2×10^9$。 #### 样例说明 样例限制上述表达式中八个变量的值，分别为：$2 \le v_1 \le 4、1 \le v_2 \le 4、v_3=0、1 \le v_4 \le 7、1 \le v_5 \le 4、1 \le v_6 \le 2、3 \le v_7 \le 4$ 和 $2 \le v_8 \le 3$。如果用二进制记数法写，最好的赋值之一给出了表达式 $(100|011|000) \& (111) \& (100|010) \& (100|011)$，从中我们可以注意到，所有子表达式可以变成等于 $7$，除了第三个。 #### 题目说明 来源于 [Baltic Olympiad in Informatics 2006](https://www.cs.helsinki.fi/group/boi2006/) 的 [Day 1:Bitwise](https://www.cs.helsinki.fi/group/boi2006/tasks/bitwise.pdf)。 由 @[求学的企鹅](/user/271784) 翻译整理。