ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

УрКОП 2020

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Tax Fees

Time limit: 1.0 second
Memory limit: 256 MB
If you send a package that has a weight greater than mxw, the receiver must pay a credits for each kilogram over mxw. Also, if the cost of the package is greater than mxp, the receiver must additionally pay b percent of every credit over mxp. These fees do not count towards the cost of the package.
Recently employees of SKB Kontur installed a new system that would keep track of packages and automatically calculate fees. Egor gained access to this system and now intends to earn some quick money. He wants to slightly change data of at most k packages out of n packages in the warehouse. To slightly change data is to change exactly one digit of either the weight or the cost of the package. Of course, Egor wants to maximize the total fees from every package. He’ll share a percentage of his earnings with you if you write a program for him.

Input

The first line contains two integers n and k (1 ≤ n ≤ 2 · 105), (0 ≤ kn) — the amount of packages and the maximal possible amount of changes.
The second line contains four integers mxw, mxp, a and b (1 ≤ mxw, mxp, a ≤ 109), (1 ≤ b ≤ 100).
Each of next n lines contains integers wi and pi (1 ≤ wi, pi ≤ 109) — weight and cost of i-th package.

Output

Output one real number — the maximal possible sum of tax fees from the packages. Your answer is considered correct if its absolute or relative error doesn’t exceed 10−9. Formally, if your answer is x and jury’s answer is y, your answer is considered correct if |xy|max(1, |y|) ≤ 10-9.
Then output n lines, in the i-th of them write the new weight and cost of the i-th package. If there are several possible answers, you may output any of them.

Sample

inputoutput
4 2
30 500 4 30
6 1100
60 90
9 990
91 420
3217.000000000
6 9100
60 90
9 990
91 920
Problem Author: Ivan Sychev
Problem Source: Ural School Programming Contest 2020
To submit the solution for this problem go to the Problem set: 2152. Tax Fees