URI Online Judge | 1798 | [P2]

Cortando Canos

Por Lucas Hermann Negri, Universidade Tecnológica Federal - Paraná BR Brazil

Timelimit: 2

A OBI (Organização Brasileira de Instalações) é uma empresa que atua na área de produção de tubos e conexões. A técnica de produção utilizada na OBI produz sempre canos longos, que são então cortados para satisfazer a necessidade dos clientes.

Os seus clientes tem aplicações variadas, necessitando de diferentes comprimentos de canos. No início, quando a empresa era pequena e os clientes eram poucos, todo o processo de planejamento dos cortes (para maximizar o lucro) era efetuado por um funcionário muito dedicado. Porém, com o aumento dos pedidos, isto se tornou proibitivo. É aí que você entra: contratado pela OBI, sua tarefa é escrever um programa que, dada uma relação de comprimentos de cano e seus respectivos valores de venda, determine o maior valor total que possa ser obtido com o corte de um cano de comprimento inicial determinado. Comprimentos de cano podem ser repetidos, e podem haver sobras de cano.

Entrada

A entrada é iniciada por um linha contendo o inteiro N (1 ≤ N ≤ 1000) que é o número de tamanhos de canos solicitados e o inteiro T (1 ≤ T ≤ 2000) que é o tamanho do cano produzido pela OBI.

A seguir virão N linhas, cada uma contendo dois inteiros Ci e Vi (1 ≤ Ci, Vi ≤ 5000, 1 ≤ iN), representando, respectivamente, o comprimento do cano i desejado por um cliente e seu valor de venda.

Saída

Imprima em uma linha o maior valor que pode ser obtido com o corte e a venda o cano original de tamanho T.

Exemplo de Entrada Exemplo de Saída

3 10
6 3
2 1
5 2

5