# 2532 - Demogorgon
- **ID**: 2532
- **IdBecrowd**: 2532
- **Tags**: geometria, programacao-dinamica
- **Nível**: 6
- **Tempo Limite**: 1 segundos
- **Memória**: 200 MB
- **Categoria**: Paradigmas
- **Autor**: Por Ricardo Oliveira, UFPR  Brasil

## Descrição
Você está progredindo muito bem em sua grande jornada com um mago na terra da fantasia. Entretanto, um novo desafio acabou de aparecer: um demogorgon, príncipe dos demônios, surgiu em sua frente! Para progredir, você deve derrotá-lo!

                    Para derrotar o demogorgon, você precisa tirar todos os 
P
 pontos de vida (HP) do monstro. Para tal, você tem à disposição 
N
 feitiços, numerados de 1 a 
N
. Utilizar o feitiço 
i
 causa 
D
i
 pontos de dano, isto é, os pontos de vida (HP) do monstro são decrementados em 
D
i
 unidades se o feitiço 
i
 é utilizado. Para utilizar o feitiço 
i
, você precisa gastar 
M
i
 mana (uma quantidade de energia mágica). Cada feitiço pode ser utilizado no máximo uma vez.
                

Dados os pontos de vida do demogorgon e os feitiços que você pode utilizar, determine a quantidade mínima de mana necessária para derrotar o monstro.

## Entrada
A primeira linha de cada caso de teste contém dois inteiros 
N
 e 
P
 (1 ≤ 
N
 ≤ 1000, 1 ≤ 
P
 ≤ 2000), o número de feitiços disponíveis e os pontos de vida (HP) do monstro, respectivamente. As próximas 
N
 linhas descrevem um feitiço cada. Cada linha contém dois inteiros 
D
i
 e 
M
i
 (1 ≤ 
D
i
, 
M
i
 ≤ 1000), o dano causado pelo feitiço e a quantidade de mana necessária para utilizá-lo, respectivamente. A entrada termina com fim-de-arquivo (EOF).

## Saída
Para cada caso de teste, se é impossível derrotar o monstro, imprima uma linha com -1. Caso contrário, imprima uma linha com a quantidade mínima de mana necessária para derrotar o monstro.

## Exemplos
### Exemplo de Entrada
```
3 10

                                5 30

                                2 20

                                6 40
                            

                            2 100

                            50 1

                            49 100
```

### Exemplo de Saída
```
70

-1
```