비트 연산식

신호 처리에서는 각 변수가 주어진 범위의 정수일 때, 비트 AND과 OR 연산자로 이루어진 식이 가질 수 있는 최댓값이 필요할 때가 있습니다. 이러한 식과 각 변수의 범위를 입력받아, 식이 가질 수 있는 최댓값을 구하는 프로그램을 작성하세요.

식의 형태는 항상 동일합니다. 여러 개의 부분식을 각각 괄호로 묶고 비트 AND 연산자(&)로 연결합니다. 각 부분식은 하나 이상의 변수를 비트 OR 연산자(|)로 연결한 것입니다. 이 형태 덕분에, 부분식의 개수와 각 부분식이 포함하는 변수의 개수만으로 식 전체를 완전히 나타낼 수 있습니다. 변수는 식에 나타나는 순서대로 번호가 매겨집니다.

예를 들어 부분식이 4개이고 각각 3, 1, 2, 2개의 변수를 포함하면 식은 다음과 같습니다.

E = (v1 | v2 | v3) & (v4) & (v5 | v6) & (v7 | v8)

비트 연산자는 통상적인 방식으로 동작합니다. 21 & 6을 계산하려면 두 수를 이진수 10101과 00110으로 쓰고, 결과의 각 자리는 두 피연산수 모두 1일 때만 1이 되어 00100 = 4가 됩니다. 21 | 6은 두 피연산수 중 적어도 하나가 1이면 결과 자리가 1이 되어 10111 = 23이 됩니다. 이 규칙은 세 개 이상의 피연산수에도 그대로 확장됩니다. 예를 들어 30 & 11 & 7 = 2입니다.

                    11110  10101    10101    01011& 00110  | 00110  & 00111-------  -------  -------  00100    10111    00010

첫째 줄에 두 정수 N과 P가 주어집니다. N은 변수의 총 개수(1 ≤ N ≤ 100), P는 부분식의 개수(1 ≤ P ≤ N)입니다. 둘째 줄에는 P개의 정수 K1 … KP가 주어지며, Ki는 i번째 부분식에 포함된 변수의 개수입니다. 모든 Ki는 1 이상이고 그 합은 N과 같습니다. 이어지는 N개의 줄에는 각각 두 정수 Aj와 Bj(0 ≤ Aj ≤ Bj ≤ 2 000 000 000)가 주어지며, 이는 j번째 변수의 범위 Aj ≤ vj ≤ Bj를 나타냅니다.

식이 가질 수 있는 최댓값을 한 줄에 정수 하나로 출력합니다.

위 식에서 범위가 2 ≤ v1 ≤ 4, 1 ≤ v2 ≤ 4, v3 = 0, 1 ≤ v4 ≤ 7, 1 ≤ v5 ≤ 4, 1 ≤ v6 ≤ 2, 3 ≤ v7 ≤ 4, 2 ≤ v8 ≤ 3이라고 합시다. 한 최적 할당에서는 세 번째 부분식을 제외한 모든 부분식이 7에 도달할 수 있지만 세 번째 부분식은 7에 도달할 수 없으므로, 부분식들의 AND, 즉 답은 6이 됩니다.