← 返回题目列表

Codeforces · 767/E

E. 无需更改

中文机器翻译题面 查看原题

学生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