553. Sultan's Pearls
Time limit per test: 1
Memory limit: 262144
Sultan Suleiman was so rich that legends spread far and wide about his treasures. This problem is going to be about one of those legends.
One of the sultan's favorite treasures was a string of finest pearls that he kept on the bedside table. He never touched the string as it had too many pearls on it to wear. The sultan's cunning servant decided to take advantage of this fact and "borrow" a few pearls. The string consisted of n
of them hung down from the bedside table. In this problem we will consider the pearls indexed by integers from 1 to n
, starting from the end that lies on the table, that is, pearls 1, 2,..., n
were located on the table and pearls n
hung down from it.
Sample for n=10 and m=3.
The servant decided to take exactly one pearl from one end of the string every day. But he had to be perfectly careful as every evening the sultan enjoyed looking at the string and counting the number of the hanging pearls. That's why after the servant took a pearl from the hanging end, he had to pull the string one pearl lower so that the number of the hanging pearls equalled m
again. Certainly, if the servant took a pearl from the lying end, he had to leave the hanging part as it was.
Each pearl has some mass, and the string may fall down if the hanging part is too heavy. Of course, the servant must avoid that. The string must remain motionless after every action of the servant.
More formally, assume that the i
-th pearl in the string has mass of wi
. Also let's say that the total mass of the hanging m
pearls equals Wh
, and the total mass of the pearls on the table equals Wt
. Then the hanging part pulls the whole string down, if Wh
, where k
is the coefficient of friction of the pearls against the table. The coefficient k
is the same for all pearls.
The pearls on the string had not only different masses but also different prices: the i
-th pearl costs ci
dinars. The servant's aim was to steal the pearls for the maximum sum and avoid the sultan's suspicions. His plan didn't come out very well: he made a mistake somewhere in his calculations, his theft was discovered and he was executed.
Nobody is going to execute you, of course, so we suggest you to solve the problem that proved to be too hard for the sultan's servant.
The first line contains three integers n
(2 ≤ n
≤ 2 · 105
, 1 ≤ m
, 1 ≤ k
≤ 10). Each of the following n
lines contains two integers wi
— the mass and the price of the i
-th pearl (1 ≤ wi
≤ 1000). It is guaranteed that initially the string is motionless, that is, the hanging part doesn't pull the whole string down.
In the first line print two space-separated integers p
— the number of pearls you can take to get the maximum sum of money, and the sum you can get. In the second line print the string consisting of p
' or '
'. If the pearl that is the i
-th to take should be taken from the hanging end, then the i
-th character of the string must be '
', otherwise — '
'. If there are multiple optimal solutions, print any of them.
If the servant can't take any pearl, just print one line containing two zeroes. You may leave the second line empty or do not print it at all.
5 2 1
20 7 2
There is the explanation to the second sample.
Initially the mass of pearls on the table was Wt
= 50, and the mass of the hanging pearls was Wh
= 51. However, as the coefficient of friction equals 2, the string is motionless (50 · 2 = 100 > 51).
On the first step we take a pearl from the hanging part of the string (H
), then we need to pull the string one pearl lower so that the hanging part contained 7 strings again. After that Wt
= 48, and Wh
= 43 (the pearl number 20 with value 5 will be stolen and the pearl number 13 will be the topmost pearl in the hanging part of the string).
On the second step we take a pearl from the end of the string that lies on the table (T
= 43 still, Wt
= 45, (45 · 2 > 43), the total price of the stolen treasure is S
The table describes the values of Wt
after each step.
|Step ||End ||Wt ||Wh ||S|
|3||H|| 42 ||38||11|
|4||T|| 34 ||38||15|
|5||H|| 30 ||36||19|
|6||T|| 22 ||36||24|
|7||H|| 19 ||32||30|
|8||H|| 18 ||26||32|
|9||H|| 16 ||19||46|
Note that after the 11-th step it is impossible to take any more pearls without disrupting the balance.