F - Tareas y expertos

Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Imagine una cantidad $N$ de tareas, que deben ser realizadas, cada una de ellas con determinada complejidad ci. Para hacer esto se cuenta con un grupo $M$ de expertos, caracterizados por sus respectivas capacidades $d_i$. Se sabe que el experto $i$-ésimo puede ejecutar la tarea $j$-ésima si $c_j \leq d_i$. Cada experto consume un día en hacer una tarea y ha de recibir por su trabajo una cantidad $k_i$ de pesos, que siempre es la misma independientemente del número de tareas que resuelva.El objetivo en este problema es determinar el menor tiempo posible en que se pueden resolver las $N$ tareas sin pagar más de $K$ pesos. Se asume que las tareas se pueden hacer en cualquier orden y que distintos expertos pueden trabajar al mismo tiempo en sus respectivas tareas.

Input

La primera línea de la entrada contiene tres enteros separados por un espacio $N$, $M$ ($1 \leq N, M \leq 10^5$) y $K$ ($1 \leq K \leq 10^9$) la cantidad de tareas, la cantidad de expertos y el presupuesto que se tiene. La próxima línea contiene $N$ enteros separados por un espacio que representan la complejidad de cada tarea. Después aparece una línea con $M$ enteros representando las capacidades de cada experto. En la última línea aparecen M enteros que es el dinero que cobra cada experto por trabajar. La restricciones son $1 \leq d_i, c_i, k_i \leq 10^9$.

Output

La salida es una única línea con la menor cantidad de días en que se pueden realizar todas las tareas sin pagar más que el presupuesto que tenemos. Si no es posible hacerlo con el dinero que tenemos se debe imprimir $0$.

Sample test(s)

Input
4 3 9 1 3 1 2 2 1 3 4 3 6
Output
2