Problem description

Janek dużo trenuje, aby wysokimi wynikami na konkursach programistycznych imponować znajomym dziewczynom. Na ostatnim konkursie napotkał nietypowe zadanie, które składa się z n podzadań. Za i-te podzadanie można otrzymać a_i punktów. Po wysłaniu zgłoszenia Janek otrzymuje informację o łącznej liczbie punktów, które uzyskał, ale nie dowiaduje się, które podzadania zostały zaliczone.

Janek chce odpowiedzieć na q zapytań. Każde zapytanie składa się z dwóch liczb całkowitych x oraz y, które oznaczają liczbę punktów uzyskanych przez niego w dwóch zgłoszeniach. Dla każdego zapytania Janek chciałby wiedzieć, ile maksymalnie punktów można uzyskać, uwzględniając oba zgłoszenia, przy założeniu, że każde podzadanie może zostać zaliczone tylko raz. Jeśli nie da się uzyskać takiej liczby punktów, należy wypisać  − 1.

Wejście

Na wejściu znajdują się:
Dwie liczby całkowite n oraz q — liczba podzadań oraz liczba zapytań.
n liczb całkowitych a₁, a₂, …, a_n, gdzie a_i oznacza liczbę punktów za i-te podzadanie.
q par liczb całkowitych x oraz y — wyniki dwóch zgłoszeń dla każdego zapytania.

Wyjście

Dla każdego z q zapytań wypisz jedną liczbę: Maksymalną liczbę punktów, które można uzyskać za dane zadanie, biorąc pod uwagę oba zgłoszenia.
Jeśli nie da się uzyskać dokładnie takiej liczby punktów, wypisz  − 1.

Ograniczenia

1 ≤ n ≤ 100, 1 ≤ q ≤ 5000
$\sum_{i=1}^{n} a_i \leq 1000$
$0 \leq x, y \leq \sum_{i=1}^{n} a_i$

Przykład

3 3
3 4 2
5 4
3 3
1 4

9
3
-1