Minimizar la suma


Submit solution

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

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

Karla y Sara son dos azucareras del centro que están jugando uno de sus juegos favoritos. En este juego, Karla le da a Sara un número n y n pares de enteros, el i-esimo de los cuales es (l_i, r_i). Karla quiere que Sara cree un arreglo a de longitud n tal que para cada i \; (1 \le i \le n), l_i \le a_i \le r_i . Ella también quiere que Sara minimice la suma:

\displaystyle \sum_{i=2}^n|a_i - a_{i-1}|

Ya que Sara está muy ocupada, ella solicita su ayuda para encontrar la mínima suma entre todos los arreglos que satisfagan la condición de Karla.

Entrada

La primera línea de la entrada contiene al entero n. La segunda línea contiene n enteros l_1, l_2, ..., l_n, separados entre sí por un espacio en blanco. De forma similar, la tercera línea contiene n enteros r_1, r_2, ..., r_n, separados entre sí por un espacio en blanco.

Salida

Imprima un entero simple que represente a la suma mínima.

Restricciones

  • 2 \le n \le 10^5
  • 1 \le l_i  \le r_i \le 10^9

Ejemplo de Entrada

5
1 2 6 1 2
3 5 8 2 3

Ejemplo de Salida

7

Explicación

El arreglo final es [a_1, a_2, a_3, a_4, a_5] y en la entrada podemos apreciar que:

1 \le a_1 \le 3

2 \le a_2 \le 5

6 \le a_3 \le 8

1 \le a_4 \le 2

2 \le a_5 \le 3

Para minimizar la suma |a_1 - a_2| + |a_2 - a_3| + |a_3 - a_4| + |a_4 - a_5|, podemos elegir nuestro arreglo como [3, 3, 6, 2, 2]. Entonces |3 - 3| + |6 - 3| + |2 - 6| + |2 - 2| es igual a 7.


Comments

There are no comments at the moment.