카라반 여행 계획

카라반 경로는 하루 이동 거리보다 조금 짧은 간격으로 늘어선 야영지의 순서이다. 각 야영지는 물이 적은 건조 야영지이거나, 물과 가축 사료가 풍부한 오아시스이다. 카라반 여행은 항상 오아시스에서 출발해 오아시스에서 끝나며, 지나온 야영지로 되돌아가지 않는다. 카라반 여행은 목적지 오아시스와 그곳에 도착하는 데 걸리는 일수로 정해진다. 예를 들어 오아시스가 2, 3, 5, 7, 11번 야영지에 있고, 카라반이 10일 뒤에 7번 야영지에서 다른 카라반과 만나려 한다고 하자. 이때 카라반은 3일을 기다렸다가 곧장 7번 야영지로 갈 수 있고, 지금 출발해 7번 야영지에서 3일을 기다릴 수 있으며, 2, 3, 5번 야영지에서 각각 하루씩 기다릴 수도 있다. 카라반 여행 계획은 매일 밤 어느 야영지에 머물지를 정한 것이다. 예를 들어 2, 3, 5번 야영지에서 각각 하루씩 기다리면 여행 계획은 1, 2, 2, 3, 3, 4, 5, 5, 6, 7이 된다.

오아시스가 2, 3, 5, 7, 11번 야영지에 있을 때, 5번 야영지까지 7일이 걸리는 여행에는 아래와 같이 10가지 여행 계획이 있다. 0은 출발 지점에서 쉬는 것을 뜻한다.

0012345, 0122345, 0123345, 0123455, 1222345, 1223345, 1223455, 1233345, 1233455, 1234555

카라반 경로 위 오아시스의 위치와, 여행마다 목적지 번호와 소요 일수가 주어질 때, 각 여행에 대해 서로 다른 여행 계획의 수를 구하는 프로그램을 작성하라.

첫 줄에는 공백으로 구분된 두 정수 $N$과 $M$이 주어진다. $N$은 주어질 오아시스 위치의 개수이고, $M$은 여행 계획 수를 구할 카라반 여행의 개수이다. $5 \le N \le 20$, $1 \le M \le 10$.

둘째 줄에는 각 오아시스까지의 일수 $O_n$이 공백으로 구분되어 오름차순($O_{n-1} < O_n$)으로 주어진다. $1 \le O_n \le 60$.

나머지 $M$개 줄에는 각각 공백으로 구분된 두 정수 $D_m$과 $T_m$이 주어진다. $D_m$은 목록에서 목적지 오아시스의 번호이고, $T_m$은 그곳에 도착하는 데 걸리는 일수이다. $1 \le D_m \le N$, $O_{D_m} \le T_m \le 60$.

$M$개의 줄을 출력한다. $k$번째 줄에는 입력의 $k+2$번째 줄에 주어진 여행에 대해, 둘째 줄의 야영지 경로에서 가능한 서로 다른 여행 계획의 수를 정수 하나로 출력한다.