Una empresa tiene un capital inicial \(w\) y puede hacer a lo más \(k\) proyectos distintos, uno tras otro, de una lista de \(n\). El proyecto \(i\) solo se puede empezar si el capital actual es al menos \(c_i\); al terminarlo, el capital aumenta en la ganancia \(p_i\) (el capital mínimo no se gasta). Encuentra el mayor capital final posible.

Entrada

La primera línea tiene \(k\), \(w\) y \(n\) \((1 \le k, n \le 10^5, 0 \le w \le 10^9)\). La segunda tiene las ganancias \(p_i\) \((0 \le p_i \le 10^4)\) y la tercera los capitales mínimos \(c_i\) \((0 \le c_i \le 10^9)\).

Salida

El mayor capital final.

Ejemplo 1

Entrada

2 0 3
1 2 3
0 1 1

Salida

4

Ejemplo 2

Entrada

3 0 3
1 2 3
0 1 2

Salida

6