U90066 分组配对

在一个班级中，恰好有$n$名男生和$n$名女生。为了便于管理，老师给这$n$名男 生和$n$名女生分别从1到$n$进行编号。 某一天，老师在班级里开展了一项游戏。这个游戏需要将班级里的同学分成若干个不同的小组，且每个小组中需要同等数量的男生和女生。每个小组中，每一名男生需要和一名同小组的女生进行配对搭档，来完成游戏中的任务。一名男生不能和多名女生进行配对，一名女生也不能和多名男生进行配对。 老师决定采用一种比较简便的方式对全班同学进行分组：按编号顺序进行划分。具体来说，老师会确定若干个区间 $[l_1,r_1],[l_2,r_2],...,[l_k,r_k]$，满足$l_1=1,r_k=n,l_i=r_i+1(1< i \le k)$,编号处于同一个区间的男生和女生分为一组。 为了让游戏保证尽量公平，老师希望没有哪一个小组的实力过于突出。具体来说，每名同学都有一个正整数实力值，用来衡量一名同学的能力大小。当一名实力值为$a$和一名实力值$b$的女生进行配对时，这一对同学的实力值就会是$a \times b$。 而一个小组的综合实力就是这个小组中每一对同学的实力值的和。为了保证不出现综合实力过高的小组，老师希望在分组后，不论小组内如何配对，每个小组的综合实力都不会超过一个给定值$M$。 最后，为了缩短游戏进行的时间，老师希望所分的小组数量尽可能少。你需要帮助他求出：在满足上述分组规则的情况下，最少的小组数量是多少？

输入文件第一行为两个正整数$n,M$。 接下来两行，第一行为$n$个正整数$a_1 \sim a_n$,其中$a_i$表示编号为$i$的男生的实力值；第二行为$n$个正整数$b_1 \sim b_n$，其中$b_i$表示编号为$i$的女生的实力值。

输出一个整数，为最少的小组数量。输入数据保证至少存在一种满足分组规则的分组方式。

对于$10\%$的数据，满足$n \le 10$。 对于$30\%$的数据，满足$n≤ 1000$。 对于$50\%$的数据，满足$n ≤ 10000$。 对于$70\%$的数据，满足$n≤ 100000$。 对于$100\%$的数据，满足$1 ≤ n ≤ 500000，1 ≤ a_i,b_i ≤ 100000,1 ≤ M ≤10^{15}$。