CJJ 有 $n$ 天来偿还 $m$ 元的欠款，他可以选择打工赚钱或卖东西赚钱。

每天打工和卖东西所获得的报酬是不一样的。在第 $i$ 天，打工可以获得 $w_i$ 元，而卖东西可以获得 $s_i$ 元。当天赚到的钱可能为负数。

卖东西和打工都会消耗一天的时间，所以不存在上午打工，下午卖东西的情况。

由于 CJJ 希望尽快还款，他希望在最短的时间里尽快获得等于 $m$ 元的欠款。在最短时间下，CJJ 希望输出的序列字典序最小。

保证题目有解。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

第二行输入 $n$ 个正整数 $w_i$，表示第 $i$ 天打工可以赚的钱。

第三行输入 $n$ 个正整数 $s_i$，表示第 $i$ 天卖东西可以赚的钱。

输出格式

第一行输出一个整数，表示最少可以用多少天赚到 $m$ 元。

第二行输出 $n$ 个数 $1$ 或 $0$，分别表示当天打工还是卖东西。

样例 #1

样例输入 #1

3 10
3 3 3
4 4 4

样例输出 #1

3
0 1 1

提示

对于样例一的解释：

$4+3+3 = 10$

对于 $100\%$ 的数据：

• $1 \le n \le 10^5$
• $1 \le m \le 10^9$
• $-10^9 \le w_i,s_i \le 10^9$