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
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
1 100 1000
Problem Author: Vassily Burnin
Problem Source: XI USU Open Personal Contest (March 13, 2010)