553. Sultan's Pearls
Time limit per test: 1
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
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 pearls,
m 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
m were located on the table and pearls
n
m+1,
n
m+2,...,
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
ith pearl in the string has mass of
w_{i}. Also let's say that the total mass of the hanging
m pearls equals
W_{h}, and the total mass of the pearls on the table equals
W_{t}. Then the hanging part pulls the whole string down, if
W_{h} >
k ·
W_{t}, 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
ith pearl costs
c_{i} 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.
Input
The first line contains three integers
n,
m and
k (2 ≤
n ≤ 2 · 10
^{5}, 1 ≤
m <
n, 1 ≤
k ≤ 10). Each of the following
n lines contains two integers
w_{i} and
c_{i} — the mass and the price of the
ith pearl (1 ≤
w_{i},
c_{i} ≤ 1000). It is guaranteed that initially the string is motionless, that is, the hanging part doesn't pull the whole string down.
Output
In the first line print two spaceseparated integers
p and
s — 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 characters '
H
' or '
T
'. If the pearl that is the
ith to take should be taken from the hanging end, then the
ith character of the string must be '
H
', otherwise — '
T
'. 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.
Example(s)
sample input

sample output

5 2 1
5 3
4 2
6 4
3 2
2 2

2 5
TT

sample input

sample output

20 7 2
3 4
8 4
8 5
6 14
5 10
3 18
2 5
2 4
1 6
3 11
4 3
3 5
2 8
4 6
9 14
7 2
7 6
6 4
8 2
10 5

11 60
HTHTHTHHHHH

Note
There is the explanation to the second sample.
Initially the mass of pearls on the table was
W_{t} = 50, and the mass of the hanging pearls was
W_{h} = 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
W_{t} = 48, and
W_{h} = 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).
W_{h} = 43 still,
W_{t} = 45, (45 · 2 > 43), the total price of the stolen treasure is
S = 9.
The table describes the values of
W_{t},
W_{h} and
S after each step.
Step  End  W_{t}  W_{h}  S 
1  H  48  43  5 
2  T  45  43  9 
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 
10  H  14  17  52 
11  H  11  18  60 
Note that after the 11th step it is impossible to take any more pearls without disrupting the balance.