学生Arseny 喜欢提前n 天计划自己的生活。他每天都会去一家食堂,并且已经决定了接下来n天每天要点什么。食堂的价格没有变化,这意味着阿瑟尼将在第 i 天花费 ci 卢布。
流通中有 1 卢布硬币和 100 卢布纸币。此时,Arseny 有 m 个硬币和足够多的纸币(你可以假设他有无限数量的纸币)。阿尔森尼热爱现代科技,所以除了食堂之外,他在任何地方都使用信用卡,但在食堂里他必须用现金支付,因为食堂不接受刷卡。
收银员总是要求学生零钱付款。然而,这并不总是可能的,但阿尔森尼试图将收银员的不满降到最低。收银员每天的不满意程度取决于找零的纸币和硬币的总量。准确地说,如果收银员在第i天给阿森尼x张纸币和硬币,那么他对这一天的不满等于x·wi。收银员总是使用尽可能少的硬币和纸币找零,他总是有足够的硬币和纸币来做到这一点。
“小心!愤怒的收银员”
Arseny 希望以这样的方式付款:n 天收银员的总不满情绪尽可能小。帮他找出n天内的每一天他需要如何付款!
请注意,Arseny 总是有足够的钱来支付,因为他有无限数量的纸币。阿尔森尼可以在接下来的任何一天使用他收到的纸币和硬币。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 109) – Arseny 计划其行动的天数以及他当前拥有的硬币数量。
第二行包含一系列整数 c1, c2, ..., cn (1 ≤ ci ≤ 105) - Arseny 在接下来的每一天要花费的卢布金额。
第三行包含整数序列 w1, w2, ..., wn (1 ≤ wi ≤ 105) — 收银员在接下来的每一天的不满意系数。
输出
在第一行打印一个整数 - 收银员的最小可能的总体不满意。
然后打印n行,其中第i行应该包含两个数字——Arseny在第i天在食堂应该使用的纸币数量和硬币数量。
当然,阿森尼在任何一天里给收银员的钱总数应该不少于他计划花的钱数。也不应该超过 106 卢布:阿尔谢尼从来不随身携带大笔钱。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
5 42 117 71 150 243 200 1 1 1 1 1
输出 #1
79 1 17 1 0 2 0 2 43 2 0
输入 #2
3 0 100 50 50 1 3 2
输出 #2
150 1 0 1 0 0 50
输入 #3
5 42 117 71 150 243 200 5 4 3 2 1
输出 #3
230 1 17 1 0 1 50 3 0 2 0