초콜릿

어린 라나와 어린 프란이 초콜릿 공장을 방문했다. 두 사람은 초콜릿이 만들어지는 과정을 보았고, 초콜릿을 많이 맛보았으며, 이제 초콜릿을 몇 개 사려고 한다.

가게에는 서로 다른 초콜릿이 $n$개 있고, $i$번째 초콜릿의 가격은 $c_i$이다. 라나와 프란은 초콜릿을 $m$개 사려고 한다.

프란은 비용을 나누는 방법을 생각해 냈다.

• 초콜릿 가격이 $k$쿠나보다 싸면 라나가 그 값을 낸다.
• 그렇지 않으면 라나가 $k$쿠나를 내고, 프란이 나머지 $c_i - k$쿠나를 낸다.

라나가 내는 금액을 $l$, 프란이 내는 금액을 $f$라고 하자. 이 거래가 못마땅한 라나는 프란을 골탕 먹이려고 $l - f$가 최대한 작아지도록 초콜릿을 고른다. 프란이 몇 개를 살지 정하지 않았으므로, 라나는 서로 다른 $q$쌍의 $k_i$, $m_i$마다 $l - f$의 최솟값을 알고 싶어 한다.

라나가 초콜릿을 고르는 것을 도와, $q$개 질의 각각에 대해 $l - f$의 최솟값을 구하라.

첫 줄에 초콜릿의 개수 $n$과 질의의 개수 $q$가 정수로 주어진다 ($1 \le n, q \le 10^5$).

둘째 줄에는 초콜릿의 가격 $c_1, c_2, \ldots, c_q$가 순서대로 주어진다. 각 가격은 $1 \le c_i \le 10^9$을 만족한다.

다음 $q$개 줄에는 정수 $k_i$와 $m_i$가 주어진다 ($1 \le k_i \le 10^9$, $1 \le m_i \le n$). $k_i$는 프란이 정한 기준값이고, $m_i$는 살 초콜릿의 개수이다.

$q$개의 줄을 출력한다. $i$번째 줄에는 라나의 $i$번째 질의에 대한 답을 출력한다.

첫 번째 예제에 대한 설명이다. 첫 번째 질의에서 라나는 가격이 1, 9, 22, 10인 초콜릿을 고를 수 있다. 라나가 38쿠나를, 프란이 4쿠나를 내므로 답은 $38 - 4 = 34$이다. 두 번째 질의에서 라나는 가격이 22와 19인 초콜릿을 고른다. 라나가 10쿠나를, 프란이 31쿠나를 내므로 답은 $10 - 31 = -21$이다.