该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

萌萌还很小，绵羊爸爸却开始给她介绍哈密顿回路了。但是萌萌实在太小了，她还不能记住哈密顿回路的性质和许许多多的判断定理。

描述

这天，绵羊爸爸给了萌萌一个图形：一个正 N (4 ≤ N ≤ 50) 边形，将它的中心与各个顶点连线（对于给出的长度，不用考虑图形的正确性，比如绵羊爸爸可以把它放在黎曼平面上），要求萌萌从O点出发，计算出长度为L的哈密顿回路的个数。但是小萌萌并不很清楚哈密顿回路的概念，在她找到的路径中每个点（包括O点）以及每条边（共 2×N条边）都可能出现好几次或是一次都没有。小萌萌没有足够的耐心找出所有的路径，她需要你来告诉她她最多可能找到几条长度为L的不同路径。

格式

输入格式

输入的第一行，有2个正整数N,L (4 ≤ N ≤ 50; 1 ≤ L ≤ 600)，分别表示正多边形边数和需要找的路径的长度。

第二行有 N 个不超过10的正整数，表示正多边形的边长。第1个数表示顶点1到顶点2的距离，第1个数表示顶点2到顶点3的距离，依此类推，第N个数表示顶点N到顶点1的距离。

第三行有N个不超过10的正整数，表示顶点与中心连线的长度。第i个数表示中心与第i个顶点的连线长度。

输出格式

输出文件仅一行，表示不同的路径数目。结果不超过200位。

样例1

样例输入1

4 2
1 1 1 1
1 1 1 1

样例输出1

4

限制

所有测试点时限均为1000ms

来源

2009年江中信奥模拟赛