Haciendo Dinero
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 baratijas vacunas, y él puede comprar tantas de estas baratijas como su corazón desee. El tiene únicamente dinero para invertir, pero quiere maximizar su ganancia.
La Baratija de tipo i cuesta dinero para adquirir por unidad y produce de retorno por cada baratija vendida (una ganancia de ). 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 .
Considere la situación cuando GJ tiene exactamente 3 tipos de baratijas y comienza con . 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 baratijas del tipo por dinero y baratija de tipo por dinero, un total de dinero. Su ganancia sería dinero. El no puede hacer mejor que esto dado la estructura de costo y retorno.
Entrada
Línea 1: Dos enteros separados por espacio: y .
Líneas : la línea contiene dos enteros separados por espacio:
Salida
Línea : 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