A John le gustaría ir a la tienda de dulces. Le gustaría saber cuántas combinaciones de dulces puede comprar gastando todo el dinero. La tienda es muy pequeña, por lo que no hay más de tres unidades de cada tipo de dulce.

Entrada

La primera línea contiene dos enteros ~N~ y ~P~ ~(1 \leq N \leq 12, 1 \leq P \leq 10^7)~ que denota el número de dulces diferentes en el supermercado local y el efectivo total de John. La segunda línea contiene ~N~ enteros separados por espacios ~A_1, A_2, ..., A_N~ que indican la cantidad de dulces de cada tipo. La tercera línea contiene ~N~ enteros separados por espacios ~P_1, P_2, ..., P_N~ ~(1 \leq P_i \leq 2 * 10^6)~ que denota el precio de un caramelo de cada tipo.

Salida

Imprime la cantidad de maneras diferentes en que John puede comprar dulces y gastar todo el dinero.

Ejemplo de Entrada

3 16
3 1 1
5 6 1

Ejemplo de Salida

2