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