English · Original
Chinese · Translation
Formal · Original
Student Arseny likes to plan his life for _n_ days ahead. He visits a canteen every day and he has already decided what he will order in each of the following _n_ days. Prices in the canteen do not change and that means Arseny will spend _c__i_ rubles during the _i_\-th day.
There are 1\-ruble coins and 100\-ruble notes in circulation. At this moment, Arseny has _m_ coins and a sufficiently large amount of notes (you can assume that he has an infinite amount of them). Arseny loves modern technologies, so he uses his credit card everywhere except the canteen, but he has to pay in cash in the canteen because it does not accept cards.
Cashier always asks the student to pay change-free. However, it's not always possible, but Arseny tries to minimize the _dissatisfaction_ of the cashier. Cashier's dissatisfaction for each of the days is determined by the total amount of notes and coins in the change. To be precise, if the cashier gives Arseny _x_ notes and coins on the _i_\-th day, his dissatisfaction for this day equals _x_·_w__i_. Cashier always gives change using as little coins and notes as possible, he always has enough of them to be able to do this.
<center> "Caution! Angry cashier"</center>Arseny wants to pay in such a way that the total dissatisfaction of the cashier for _n_ days would be as small as possible. Help him to find out how he needs to pay in each of the _n_ days!
Note that Arseny always has enough money to pay, because he has an infinite amount of notes. Arseny can use notes and coins he received in change during any of the following days.
## Input
The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 105, 0 ≤ _m_ ≤ 109) — the amount of days Arseny planned his actions for and the amount of coins he currently has.
The second line contains a sequence of integers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ 105) — the amounts of money in rubles which Arseny is going to spend for each of the following days.
The third line contains a sequence of integers _w_1, _w_2, ..., _w__n_ (1 ≤ _w__i_ ≤ 105) — the cashier's dissatisfaction coefficients for each of the following days.
## Output
In the first line print one integer — minimum possible total dissatisfaction of the cashier.
Then print _n_ lines, the _i_\-th of then should contain two numbers — the amount of notes and the amount of coins which Arseny should use to pay in the canteen on the _i_\-th day.
Of course, the total amount of money Arseny gives to the casher in any of the days should be no less than the amount of money he has planned to spend. It also shouldn't exceed 106 rubles: Arseny never carries large sums of money with him.
If there are multiple answers, print any of them.
[samples]
学生阿尔谢尼喜欢为接下来的 #cf_span[n] 天规划生活。他每天都会去食堂，并且已经决定好接下来的 #cf_span[n] 天每天要点什么。食堂的价格不变，这意味着阿尔谢尼在第 #cf_span[i] 天将花费 #cf_span[ci] 卢布。
流通的货币包括 1 卢布硬币和 100 卢布纸币。此时，阿尔谢尼拥有 #cf_span[m] 枚硬币和足够多的纸币（你可以认为他拥有无限多）。阿尔谢尼热爱现代科技，因此他在除食堂外的所有地方都使用信用卡，但在食堂必须用现金支付，因为食堂不接受卡片。
收银员总是要求阿尔谢尼支付无需找零的金额。然而，这并不总是可行的，但阿尔谢尼会尽量最小化收银员的 _不满度_。收银员每天的不满度由找零中纸币和硬币的总数量决定。具体来说，如果收银员在第 #cf_span[i] 天给阿尔谢尼 #cf_span[x] 枚硬币和纸币作为找零，则当天的不满度为 #cf_span[x·wi]。收银员总是使用尽可能少的硬币和纸币来找零，且他总是有足够的库存来完成找零。
阿尔谢尼希望以一种方式支付，使得收银员在 #cf_span[n] 天内的总不满度尽可能小。请帮助他确定每天应该如何支付！
注意：阿尔谢尼总是有足够的钱支付，因为他拥有无限多的纸币。阿尔谢尼可以在之后的任何一天使用他收到的找零中的纸币和硬币。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ m ≤ 109]) —— 阿尔谢尼计划的天数以及他当前拥有的硬币数量。
第二行包含一个整数序列 #cf_span[c1, c2, ..., cn] (#cf_span[1 ≤ ci ≤ 105]) —— 阿尔谢尼接下来每天计划花费的卢布金额。
第三行包含一个整数序列 #cf_span[w1, w2, ..., wn] (#cf_span[1 ≤ wi ≤ 105]) —— 每天收银员的不满度系数。
第一行输出一个整数 —— 收银员可能的最小总不满度。
然后输出 #cf_span[n] 行，第 #cf_span[i] 行应包含两个数字 —— 阿尔谢尼在第 #cf_span[i] 天在食堂支付时应使用的纸币数量和硬币数量。
当然，阿尔谢尼在任何一天支付给收银员的总金额不应少于他计划的花费，也不应超过 #cf_span[106] 卢布：阿尔谢尼从不随身携带大量现金。
如果有多个答案，输出任意一个即可。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 105], #cf_span[0 ≤ m ≤ 109]) —— 阿尔谢尼计划的天数以及他当前拥有的硬币数量。第二行包含一个整数序列 #cf_span[c1, c2, ..., cn] (#cf_span[1 ≤ ci ≤ 105]) —— 阿尔谢尼接下来每天计划花费的卢布金额。第三行包含一个整数序列 #cf_span[w1, w2, ..., wn] (#cf_span[1 ≤ wi ≤ 105]) —— 每天收银员的不满度系数。
## Output
第一行输出一个整数 —— 收银员可能的最小总不满度。然后输出 #cf_span[n] 行，第 #cf_span[i] 行应包含两个数字 —— 阿尔谢尼在第 #cf_span[i] 天在食堂支付时应使用的纸币数量和硬币数量。当然，阿尔谢尼在任何一天支付给收银员的总金额不应少于他计划的花费，也不应超过 #cf_span[106] 卢布：阿尔谢尼从不随身携带大量现金。如果有多个答案，输出任意一个即可。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of days.
Let $ m \in \mathbb{Z}_{\geq 0} $ be the initial number of 1-ruble coins Arseny has.
Let $ c_i \in \mathbb{Z}^+ $ be the cost (in rubles) on day $ i $.
Let $ w_i \in \mathbb{Z}^+ $ be the dissatisfaction weight per coin/note on day $ i $.
Let $ x_i \in \mathbb{Z}_{\geq 0} $ be the number of 100-ruble notes used on day $ i $.
Let $ y_i \in \mathbb{Z}_{\geq 0} $ be the number of 1-ruble coins used on day $ i $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $, $ 0 \leq m \leq 10^9 $
2. $ 1 \leq c_i \leq 10^5 $, $ 1 \leq w_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $
3. $ 100x_i + y_i \geq c_i $ for all $ i \in \{1, \dots, n\} $
4. $ 100x_i + y_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
5. Total coins used over all days cannot exceed initial coins plus coins received as change:
$$
\sum_{i=1}^n y_i \leq m + \sum_{i=1}^n \left( \left(100x_i + y_i - c_i\right) \mod 100 \right)
$$
(since change is given optimally in coins and notes, and only coins can be retained)
**Objective**
Minimize total dissatisfaction:
$$
\sum_{i=1}^n w_i \cdot \left( \left\lfloor \frac{100x_i + y_i - c_i}{100} \right\rfloor + \left( (100x_i + y_i - c_i) \mod 100 \right) \right)
$$
Subject to the above constraints.
**Output**
Minimized total dissatisfaction and for each day $ i $: $ x_i $, $ y_i $.
API Response (JSON)
{
"problem": {
"name": "E. Change-free",
"description": {
"content": "Student Arseny likes to plan his life for _n_ days ahead. He visits a canteen every day and he has already decided what he will order in each of the following _n_ days. Prices in the canteen do not ch",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF767E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Student Arseny likes to plan his life for _n_ days ahead. He visits a canteen every day and he has already decided what he will order in each of the following _n_ days. Prices in the canteen do not ch...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "学生阿尔谢尼喜欢为接下来的 #cf_span[n] 天规划生活。他每天都会去食堂，并且已经决定好接下来的 #cf_span[n] 天每天要点什么。食堂的价格不变，这意味着阿尔谢尼在第 #cf_span[i] 天将花费 #cf_span[ci] 卢布。\n\n流通的货币包括 1 卢布硬币和 100 卢布纸币。此时，阿尔谢尼拥有 #cf_span[m] 枚硬币和足够多的纸币（你可以认为他拥有无限多）。阿尔...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of days. \nLet $ m \\in \\mathbb{Z}_{\\geq 0} $ be the initial number of 1-ruble coins Arseny has. \nLet $ c_i \\in \\mathbb{Z}^+ $ be the cost (i...",
"is_translate": false,
"language": "Formal"
}
]
}