雨滴之歌

★★★☆
输入文件：expansion.in 输出文件：expansion.out 简单对比

时间限制：1 s 内存限制：512 MiB

【题目背景】 不... 甚至都不是目的。就算某日知晓了万物的末路也不能坐视不管，那种想做些什么的心情就像源头一样存在于内心，中央就好像把那些全部相连一样。

于是... 而在那长长的连结的尾端，是我们的所处之处吗...

【题目描述】 chito 和 yuuri 仍在白色的地表上缓慢行进，直到履带下方传来一声轰响——那是雪被下冰原产生的裂缝声响。

冰原可以被看作一张 n×m 的网格图，然而在这个世界上，地图和坐标早已随人类文明远去。

万幸的是，仍有一些残余的信息，能为 chito 和 yuuri 提供些许帮助：遗迹上留下了两个分别长为 n,m 的序列 A,B，在这张网格图上，第 i 行第 j 列的冰块的 "稳定度" 为 Ai+Bj。

由于 chito 和 yuuri 要骑着摩托前行，冰块的载重量十分关键。我们认为，若 Ai+Bj≥0，那么冰块 (i,j) 是稳定的。

yuuri 想知道，是否存在一对 (s,t)(1≤s≤t≤n) 满足，可以从 (s,1) 出发，每次向右或向下走一步，并且每次经过的冰块都是稳定的，最终到达 (t,m)。如果存在这样一条道路，她们就可以沿着这条路继续前行。

chito 不满足于此，她希望有更多的备用方案。于是她想知道，有多少对 (s,t) 满足上述条件。

末世的人们并没有强大的计算工具，所以需要你来求出合法的 (s,t) 的数量。

形式化题意 给定 n×m 的网格图和序列 A1∼An,B1∼Bm，(i,j) 为黑色格子当且仅当 Ai+Bj≥0。

称一对 (s,t) 是合法的，当且仅当从 (s,1) 出发，每次向右或向下走一格，要求走到的格子均为黑色，可以到达 (t,m)。

求有多少对合法的 (s,t)。

【输入格式】 第一行两个整数 n,m。

第二行 n 个整数 A1∼An。

第三行 m 个整数 B1∼Bm。

【输出格式】 一行一个整数，表示合法的 (s,t) 数量。

【样例输入 1】 3 3 -1 0 1 -1 0 1 【样例输出 1】 1 【样例输入 2】 3 3 -1 0 1 1 0 1 【样例输出 2】 5

【数据规模与约定】 对于 20% 的数据，1≤n,m≤50。

对于 30% 的数据，1≤n,m≤300。

对于 100% 的数据，1≤n,m≤2×10^5,−10^9≤Ai,Bi≤10^9。

题目怎么做，请大佬解答。