Glotonería


Submit solution

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

Authors:
Problem type
Allowed languages
C, C++, Java, Python, VB

Tres-Veltör participará en un concurso de comer. Los equipos tienen N miembros que competirán en el concurso y el equipo de Tres-Veltör consiste de N miembros numerados de 1 hasta N desde el mas joven hasta el mas viejo. El coeficiente de consumo del miembro i es A_i.

En el concurso N comidas numeradas de 1 hasta N serán presentadas y la dificultad de la comida i es F_i. Los detalles del concurso son:

  • Un equipo debe asignar un miembro a cada comida y el mismo miembro no puede estar asignado a múltiples comidas.
  • Tomará x * y segundos para un miembro finalizar la comida donde x es el coeficiente de consumo del miembro e y es la dificultad del plato.
  • El puntaje de un equipo es el mayor tiempo que le tome a un miembro individual terminar su comida.

Antes del concurso el equipo de Tres-Veltör decidió entrenar. En una sesión de entrenamiento un miembro puede reducir su coeficiente de consumo por 1, mientras que este no sea 0. Además, por razones financieras los N miembros pueden hacer a lo mas K sesiones de entrenamiento en total.

¿Cuál es el mínimo puntaje posible que el equipo puede lograr si entrenan y se reparten los platos de forma óptima?

Límites:

1 \leq N \leq 2 \cdot 10^5

0 \leq K \leq 10^{18}

1 \leq A_i \leq 10^6 (1 \leq i \leq N)

1 \leq F_i \leq 10^6 (1 \leq i \leq N)

Entrada:

La primera línea de entrada contiene dos enteros N y K.

La segunda línea N números. El i-ésimo número es igual a A_i.

La tercera línea N números. El i-ésimo número es igual a F_i.

Salida:

Imprime el mínimo puntaje posible que el equipo puede lograr si entrenan y se reparten los platos de forma óptima.

Entrada de ejemplo 1:

3 5
4 2 1
2 3 1

Salida de ejemplo 1:

2

Ellos pueden alcanzar el puntaje de 2 de la siguiente forma:

Miembro 1 hace 4 sesiones de entrenamiento y come la comida 2 en (4 - 4) * 3 = 0 segundos

Miembro 2 hace 1 sesión de entrenamiento y come la comida 3 en (2 - 1) * 1 = 1 segundo

Miembro 3 hace 0 sesiones de entrenamiento y come la comida 1 en (1 - 0) * 2 = 2 segundos

No pueden alcanzar un puntaje menor que 2, asi que la respuesta es 2

Entrada de ejemplo 2:

3 8
4 2 1
2 3 1

Salida de ejemplo 2:

0

El equipo de Tres-Veltör puede escoger no hacer ningún entrenamiento

Entrada de ejemplo 3:

11 14
3 1 4 1 5 9 2 6 5 3 5
8 9 7 9 3 2 3 8 4 6 2

Salida de ejemplo 3:

12

Comments

There are no comments at the moment.