Es hora de pagar las cuentas, y Bruno se dio cuenta de que necesita un poco de dinero extra para comprar las casas, así que venderá algunos de sus accesorios. No quiere deshacerse de ellos, por lo que necesita tu ayuda para elegir cuáles vender.

Hay ~n~ accesorios, y el ~i-~ésimo accesorio pertenece al tipo ~r_i~ y tiene un valor ~v_i~.

Bruno debe elegir exactamente ~m~ accesorios para vender, por lo que evalúa su selección de accesorios de la siguiente manera:

• Para cada tipo de accesorio, solo se cuenta el accesorio más valioso de ese tipo.
• Si no se incluyen accesorios de un tipo, ese tipo no contribuye nada.
• La puntuación total de una selección es la suma de todos estos "accesorios más valiosos", uno por tipo.

Esta puntuación total es la belleza de la selección de Bruno.

Bruno ahora se pregunta: si considera todas las formas posibles de seleccionar exactamente ~m~ accesorios y anota la puntuación de belleza de cada selección posible, ¿cuál será la ~k-~ésima puntuación de belleza más alta en esa lista?

Entrada

La primera línea contiene tres enteros ~n~, ~m~, ~k~ (~1 \le m \le n \le 100~, ~1 \le k \le \min(2000, \binom{n}{m}~ *~)~).

La segunda línea contiene ~n~ enteros ~r_1, r_2, \ldots, r_n~ (~1 \le r_i \le n~) ~-~ el tipo de accesorio ~i~.

La tercera línea contiene ~n~ enteros ~v_1, v_2, \ldots, v_n~ (~1 \le v_i \le 10^9~) ~-~ el valor del accesorio ~i~.

* El coeficiente binomial ~\binom{n}{m}~ es igual al número de formas que se puede escoger un subconjunto de ~m~ elementos de un conjunto de ~n~ elementos diferentes. Por ejemplo, ~\binom{5}{3} = 10~ porque el conjunto ~\{1,2,3,4,5\}~ tiene ~10~ subconjuntos de ~3~ elementos.

Salida

Imprime un solo entero ~-~ la ~k-~ésima puntuación de belleza más grande entre todas las selecciones posibles de exactamente ~m~ accesorios.

Subtareas

Subtarea	Puntos	Restricciones adicionales	Dependencias
~1~	~2~	~m = 1~	~-~
~2~	~7~	~m \le 3~	~1~
~3~	~10~	~n \le 20~	~-~
~4~	~9~	~\binom{n}{m} \le 10^6~	~1-3~
~5~	~7~	~r_i = 1~ para cada ~i~ tal que ~1 \le i \le n~	~-~
~6~	~9~	~r_i \in \{1,2\}~ para cada ~i~ tal que ~1 \le i \le n~	~5~
~7~	~15~	~k = 1~	~-~
~8~	~21~	~k \in \{1,2\}~	~7~
~9~	~20~	Sin restricciones adicionales.	~1-8~

Ejemplos

Entrada 1

4 2 1
1 1 2 2
3 5 4 6

Salida 1

11

Entrada 2

4 2 3
1 1 2 2
3 5 4 6

Salida 2

9

Entrada 3

4 3 2
1 1 2 2
3 5 4 6

Salida 3

11