P7637 [BalticOI 2006] BITWISE EXPRESSIONS (Day 1)

In signal processing, when variables are integers within certain ranges, people are sometimes interested in the maximum value of an expression that contains bitwise AND and OR operators. You need to write a program that takes such an expression and the range of each variable as input, and determines the maximum value the expression can take.

For simplicity, the expression has a specific form: it consists of several subexpressions in parentheses, separated by the bitwise AND operator (denoted by $\&$). Each subexpression consists of one or more variables, separated by the bitwise OR operator (denoted by $|$). With this convention, the expression can be fully specified by giving the number of subexpressions and the number of variables in each subexpression. Variables are numbered only according to their occurrences in the expression. For example, if the number of subexpressions is $4$, and the numbers of variables in each subexpression are $3$, $1$, $2$, $2$, then the expression is: $$E=(v_1|v_2|v_3) \& (v_4) \& (v_5|v_6) \& (v_7|v_8)$$ Bitwise operators are defined in the usual way. For example, to compute $21 \& 6$, we first write the numbers (operands) in binary: $10101$ and $110$ (because $21=2^4+2^2+2^0$ and $6=2^2+2^1$). Each binary digit of the result now depends on the corresponding digits of the operands: if both operands have $1$, then the result digit is $1$, otherwise it is $0$. As shown on the left in the figure below, the result is $4$. If we want to compute $21| 6$, the process is the same, except that if the corresponding digit is $1$ in any operand, then the result is $1$. Therefore, the result digit is $0$ only when both operands have $0$. As shown in the middle of the figure below, the result is $23$. Extending this to more than two operands is straightforward. The example on the right below shows that $30 \& 11 \& 7=2$. 

The first line contains two positive integers $N$ and $P$. The second line contains $P$ positive integers ($K_1,K_2, \cdots ,K_P$), where $K_i$ is the number of variables in the $i$-th subexpression. Each $K_i$ is at least $1$, and their sum equals $N$. The next $N$ lines each contain two integers $A_j$ and $B_j$, specifying the value range of the $j$-th variable in the expression by $A_j \le v_j \le B_j$.

One line containing one integer: the maximum value the expression can take.

#### Constraints For $100 \%$ of the testdata, $1 \le N \le 100$, $1 \le P \le N$, $0 \le A_j \le B_j \le 2×10^9$. #### Sample Explanation The sample restricts the values of the eight variables in the expression as follows: $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$, and $2 \le v_8 \le 3$. If written in binary, one of the best assignments gives the expression $(100|011|000) \& (111) \& (100|010) \& (100|011)$. From this we can see that all subexpressions can become equal to $7$ except the third one. #### Problem Notes From [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). Translated and organized by @[求学的企鹅](/user/271784). Translated by ChatGPT 5