Oportunidade

Pedro está passando por uma série de dificuldades financeiras, de modo que precisa se desfazer de seu estabelecimento comercial. Ele ofereceu a Carlos uma excelente oportunidade: que ele assumisse o negócio, sem custos desta transação, pedindo a ele apenas que transferisse toda a documentação e se responsabilizasse pelas dívidas com os fornecedores.

Carlos ficou animado com a possibilidade, mas não dispunha de nenhum capital no momento. Após uma visita ao seu gerente de banco, Carlos apurou que ele pode contrair um empréstimo de, no máximo, $M$ reais.

Sendo um homem prudente, e de posse de uma lista de $N$ eventos (despesas ou receitas) do estabelecimento previstos para os meses seguintes, Carlos quer saber qual é a quantia mínima que ele deve pedir emprestado ao banco para que ele consiga manter o negócio pagando as despesas em dia, sem atrasos e sem a possibilidade de adiantar receitas, lembrando que ele não dispõe de nenhum dinheiro no caixa.

Entrada

A primeira linha da entrada contém os inteiros $M$ ($1 \leq M \leq 10^9$) e $N$ ($1 \leq N \leq 2\times 10^5$), separados por um espaço em branco. Estes inteiros representam, respectivamente, a quantia máxima, em reais, que ele pode pedir emprestado no banco e o número de eventos que acontecerão no meses seguintes.

A próxima linha contém $N$ valores $v_i$ ($-10^4 \leq v_i \leq 10^4$) de cada um dos eventos financeiros que acontecerão naquele mês, em reais e separados por um espaço em branco, sendo que valores negativos representam despesas e valores positivos representam receitas. Os eventos são dados em ordem cronológica, um por dia, do primeiro ao último.

Saída

Imprima, em uma linha, o valor mínimo, em reais, que Carlos deve pedir emprestado no banco para que ele consiga manter o estabelecimento segundo os critérios citados. Caso não seja possível obter o valor necessário, deve ser impresso o valor -1.

Exemplo de entrada 1

1000 5
100 -250 75 -320 1000

Exemplo de saída 1

395

Explicação do exemplo 1: No primeiro caso, ao pegar 395 reais emprestados, Carlos recebe mais 100 reais no primeiro dia, totalizando 495 reais. No dia seguinte, paga uma dívida no valor de 250 reais e depois ganha mais 75, ficando com um saldo de 320, o suficiente para pagar a próxima dívida. Por fim, fecha os eventos recebendo 1000, o seu saldo final.

Exemplo de entrada 2

100 3
100 200 100

Exemplo de saída 2

0

Explicação do exemplo 2: No segundo caso, todos os eventos são créditos a receber, de modo que não é necessário pegar nenhum empréstimo.

Exemplo de entrada 3

2000 10
-500 380 40 -200 80 170 -350 100 200 70

Exemplo de saída 3

500

Explicação do exemplo 3: No terceiro caso, ele deve pegar 500 reais para pagar já a primeira dívida. Após ela, a sequência de créditos a receber é suficiente para pagar as dívidas futuras.

Exemplo de entrada 4

100 9
40 30 20 10 -150 60 25 -240 1000

Exemplo de saída 4

-1

Explicação do exemplo 4: No quarto caso o empréstimo máximo que poderia ser obtido é de 100 reais, o que não é suficiente para quitar a dívida de 240 reais a ser paga no oitavo dia.