Change-free
Contest: Codeforces Round 398 (Div. 2)
Difficulty rating: 2400
Tags: greedy

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 ci 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·wi. Cashier always gives change using as little coins and notes as possible, he always has enough of them to be able to do this.

"Caution! Angry cashier"

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 format:
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 c1, c2, ..., cn (1 ≤ ci ≤ 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 w1, w2, ..., wn (1 ≤ wi ≤ 105) — the cashier's dissatisfaction coefficients for each of the following days.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
5 42
117 71 150 243 200
1 1 1 1 1

Example output:
79
1 17
1 0
2 0
2 43
2 0

Example input:
3 0
100 50 50
1 3 2

Example output:
150
1 0
1 0
0 50

Editorial:
The first thing to note is that during day i it makes sense to either pay $$c_i \div 100$$ notes и $${ c _ { i } \mod 100 }$$ coins (in this case, the cashier's dissatisfaction would be equal to 0), or just $$c_{i} \operatorname{div} 100 + 1$$ notes (in that case, the cashier's dissatisfaction would be equal to $$(100 - (c_i \bmod 100)) w_i$$)/ Moreover, the second case is impossible if $${ c _ { i } \mod 100 = 0 }$$, so in that case you just have to pay the required amount of notes.
In order to solve the problem, we have to note the additional fact. Let's suppose Arseny paid change-free during the i-th day and gave the cashier $${ c _ { i } \mod 100 }$$ coins. Then, if we change the payment way this day, the amount of coins availible to Arseny would increase by 100 regardless of the ci! Indeed, Arseny wouldn't spend those $${ c _ { i } \mod 100 }$$ coins, and he would aso receive $$100 - ( c_{i} \bmod 100)$$ coins in change, which adds up to exactly 100 coins.
Let's build the optimal solution day-by-day beginning from day one, trying to pay change-free every time to minimize the cashier's dissatisfaction. Let i-th day be the first one when Arseny wouldn't be able to pay change-free. It means that Arseny has to get some change at least once during days from first to i-th. But, regardless of the day, after i-th day he would have the same amount of coins! It means that the optimal way is to get change during the day when the cashier's dissatisfaction would be minimal. Then, let's continue to pay change-free whenever we can. If Arseny again can't pay change-free during day j, there must be a day from first to j-th when he got change. Using similiar considerations, whe should choose the day with the minimal cashier's dissatisfaction (except the first one). We should do these operations until we process all days.
The simple implementation of this process works in O(n2) time and hits TLE. But if you use any structure of data which allows you to add or delete element or find minimum in $${\mathcal {O}}(\log n)$$ time, for example, heap or binary seach tree, we can save all previous days into it and find a day with the minimal cashier's dissatisfaction faster than O(n). The final time is $$O(n \log n)$$.