题目描述

一辆公交车从 1 号站依次开往 2 号站、3 号站…… 直到 n 号站。每一站会先下车 bi​ 人，再上车 ai​ 人。公交车除司机外最多可乘坐 m 人。

请判断：在行驶过程中的任意时刻，车上人数是否会超过限载人数。若会超载，输出 0；否则输出 1。

输入格式

第一行两个整数 n,m，表示车站数量与限载人数。第二行 n 个整数 a1​,a2​,…,an​，表示每站上车人数。第三行 n 个整数 b1​,b2​,…,bn​，表示每站下车人数。

1≤n≤1e5,1≤ai,bi,m≤1e9

输出格式

若某时刻车会超载，请输出0，否则输出1；

样例

5 12
1 2 3 12 5
0 1 2 3 4

0