|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
A - Organizando Cajas
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Fito ha comenzado a trabajar en el almacén de un hotel cerca de su casa. La primera tarea que le dan es ordenar todas las cajas de una sección del almacén. Como es su primer día de trabajo, Fito quiere cumplir esta orden de la mejor forma posible. Para esto decide que la manera adecuada de ubicar las cajas es ponerlas todas las cajas formando una sola columna, logrando así mayor espacio en el almacén. De cada caja se sabe su peso y su fuerza. El riesgo de que una caja se rompa se calcula como el peso total de las cajas encima de ella menos la fuerza de la caja. Como Fito sabe que si se rompe una caja la tiene que pagar él entonces necesita ordenar las cajas de forma tal que el mayor riesgo de que se rompa alguna de ellas sea mínimo.
Input
La primera línea de la entrada contiene un entero $N$ ($1 \leq N \leq 50000$) la cantidad de cajas que Fito debe ordenar. Después sigue N líneas cada una con un par de enteros separados por un espacio: $W_i$ ($1 \leq Wi \leq 10000$) y $S_i$ ($1 \leq S_i \leq 10^9$) el peso y la fuerza de la caja $i$ respectivamente.
Output
La salida consiste en un entero: el mayor riesgo en el orden de Fito.
Sample test(s)
Input
3
10 3
2 5
3 3
Output
2