Caravan Trip Plans

A caravan route is a sequence of camping locations spaced a bit less than a day's travel apart. Each camping location is either a dry camp with little water or an oasis with plentiful water and perhaps fodder for animals. A caravan trip always starts and ends at an oasis and never goes back to a previous camp. A caravan trip is defined by a destination oasis and the number of days needed to get there. For example, if the oases are at camps 2, 3, 5, 7, 11, and a caravan wants to meet another caravan at camp 7 in 10 days, the caravan can wait 3 days and then go directly to camp 7, or leave now and wait 3 days at camp 7, or wait 1 day at each of camps 2, 3, and 5. A caravan trip plan is the choice of which camp to stay at each night. For example, waiting 1 day at each of camps 2, 3, and 5 gives the trip plan 1, 2, 2, 3, 3, 4, 5, 5, 6, 7.

With oases at camps 2, 3, 5, 7, 11, a 7 day trip to camp 5 has 10 trip plans, listed below (0 means resting at the start):

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

Write a program that takes the locations of the oases on a caravan route and a list of trip destinations with their travel days, and outputs the number of distinct trip plans for each trip.

The first line contains two space-separated integers $N$ and $M$. $N$ is the number of oasis locations to be given, and $M$ is the number of caravan trips whose plans are to be counted. $5 \le N \le 20$, $1 \le M \le 10$.

The second line contains $N$ space-separated integers $O_n$, the number of days to each oasis, in increasing order ($O_{n-1} < O_n$). $1 \le O_n \le 60$.

Each of the remaining $M$ lines contains two space-separated integers $D_m$ and $T_m$. $D_m$ is the index of the destination oasis in the list, and $T_m$ is the number of days to get there. $1 \le D_m \le N$, $O_{D_m} \le T_m \le 60$.

Output $M$ lines. The $k$-th line contains one integer, the number of distinct trip plans for the trip given on input line $k+2$, over the camp route given on the second input line.