beecrowd | 2532

Demogorgon

Por Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

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 Di pontos de dano, isto é, os pontos de vida (HP) do monstro são decrementados em Di unidades se o feitiço i é utilizado. Para utilizar o feitiço i, você precisa gastar Mi 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 Di e Mi (1 ≤ Di, Mi ≤ 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.

Exemplo de Entrada Exemplo de Saída

3 10
5 30
2 20
6 40

2 100
50 1
49 100

70

-1