Haciendo Dinero


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

GJ se ha introducido en el negocio de baratijas, comprando y vendiendo baratijas como adornos navideños vacunos. El sabe que venderá cada baratija que él pueda almacenar de un catalogo de N (1 \leq N \leq 1000) baratijas vacunas, y él puede comprar tantas de estas baratijas como su corazón desee. El tiene únicamente M (1 \leq M \leq 100,000) dinero para invertir, pero quiere maximizar su ganancia.

La Baratija de tipo i cuesta C_i (1 \leq C_i \leq 100,000) dinero para adquirir por unidad y produce R_i (1 \leq R_i \leq 100,000) de retorno por cada baratija vendida (una ganancia de R_i-C_i). GJ puede mezclar y aparear las baratijas que él vende de cualquier manera que él desee. El no necesita gastar todo su dinero cuando compra baratijas.

¿Cuál es la cantidad más grande de ganancia total según la fórmula

ganancia = (dinero_inicial) – (los costos de todas las ventas) + (ganancia de todas las ventas)

que GJ puede tener al final del primer año? Se garantiza que este número será menor que 1,000,000,000.

Considere la situación cuando GJ tiene exactamente 3 tipos de baratijas y comienza con M=17. A continuación están los costos y retornos para cada baratija:

       Baratija    Costo     Retorno
           #        C_i       R_i
           1         2         4
           2         5         6
           3         3         7

En este caso, GJ debería comprar 5 baratijas del tipo 3 por 15 dinero y 1 baratija de tipo 1 por 2 dinero, un total de 17 dinero. Su ganancia sería 5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22 dinero. El no puede hacer mejor que esto dado la estructura de costo y retorno.

Entrada

Línea 1: Dos enteros separados por espacio: N y M.

Líneas 2:..N+1: la línea i+1 contiene dos enteros separados por espacio: C_i y R_i

Salida

Línea 1: La ganancia máxima que GJ puede generar dados los costos y retornos

Ejemplo de Entrada

3 17
2 4
5 6
3 7

Ejemplo de Salida

22

Comments

There are no comments at the moment.