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

USU Open Personal Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Gold Bars

Time limit: 0.5 second
Memory limit: 64 MB
Mary is a storekeeper at a jewelry factory. Her computer keeps track of the remainders of batches of gold bars. The weight and fineness (the content of gold in 1 kilogram of alloy measured in grams) is known for each gold bar.
A foundry worker comes to Mary and tells that he needs to cast a bar of fineness p and weight m grams. He can take from the storehouse any part of any bar for his purpose.
Write a program for automatizing this operation.


The first line contains integers n, m, and p (1 ≤ n ≤ 1000; 1 ≤ m ≤ 1 000 000; 0 ≤ p ≤ 1000). The following n lines describe the gold bars at the storehouse, one bar per line. The description of a bar contains its weight mi in grams and its fineness pi (1 ≤ mi ≤ 1000; 0 ≤ pi ≤ 1000).


If it is possible to satisfy the worker's requirement, output “YES” in the first line. In the following n lines specify the numbers xi, one per line, which are the weights in grams of the parts that should be taken from each bar. Output these numbers with the maximal possible accuracy. The answer will be considered correct if the following conditions will be satisfied:
Problem illustration
If there are several ways to cast a required bar, output any of them.
If it is impossible to satisfy the worker's requirement, output “NO” in the only line.


4 150 750
100 1000
150 585
100 750
100 0
1 100 1000
200 0
Problem Author: Vassily Burnin
Problem Source: XI USU Open Personal Contest (March 13, 2010)
To submit the solution for this problem go to the Problem set: 1757. Gold Bars