Problem description

Jasio wraz z przyjaciółmi grają w swoją ulubioną grę karcianą Dołóż kartę.

Pewnie nigdy nie grałeś/aś w tę grę, więc pokrótce przedstawimy jej zasady. Każda z N osób siedzących w kółku ma w ręce jedną kartę, którą w swojej turze może dorzucić do stosu (jeśli to zrobi, to w ręce nie będzie już miała żadnych kart). Celem graczy jest takie dorzucanie kart do stosu, aby ich suma wyniosła K. Oczywiście chcą to zrobić w minimalnej możliwej liczbie tur. Rozgrywkę rozpoczyna gracz P-ty, potem kolej gracza P + 1-szego itd. Po N-tym graczu następuje tura 1-szego gracza, potem 2-giego itd.

Twoim zadaniem jest wyznaczenie minimalnej potrzebnej liczby tur.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, będące odpowiednio liczbą graczy oraz liczbą gier, które rozegrają. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A₁, A₂, …, A_N, odpowiadających wartościom kart w rękach graczy. W i-tym z kolejnych Q wierszy znajdują się dwie liczby naturalne P_i oraz K_i, będące odpowiednio indeksem rozpoczynającego gracza oraz wymaganą do osiągnięcia sumą.

Wyjście

W i-tym wierszu należy wypisać odpowiedź dla i-tej rozgrywki.

Powinna być ona minimalną potrzebną liczbą tur, aby możliwe było osiągnięcie sumy wynoszącej K. Jeżeli jest to niemożliwe należy wypisać 0.

Ograniczenia

1 ≤ N ≤ 2000, 1 ≤ Q ≤ 500 000, 1 ≤ P_i ≤ N, 1 ≤ A_i, K_i ≤ 5000.

Przykład

5 2
2 4 8 6 2
5 6
2 7

3
0