<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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 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 > k · Wt, 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.

Input
The first line contains three integers n, m and k (2 ≤ n ≤ 2 · 105, 1 ≤ m < n, 1 ≤ k ≤ 10). Each of the following n lines contains two integers wi and ci — the mass and the price of the i-th pearl (1 ≤ wi, ci ≤ 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 space-separated 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 i-th to take should be taken from the hanging end, then the i-th 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 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). Wh = 43 still, Wt = 45, (45 · 2 > 43), the total price of the stolen treasure is S = 9.

The table describes the values of Wt, Wh and S after each step.





Step	End	Wt	Wh	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 11-th step it is impossible to take any more pearls without disrupting the balance.

<|response|>
1. Abridged problem statement  
We have a row of n pearls, initially the first n–m lie on a table and the last m hang off the table. Each pearl i has weight w[i] and value c[i]. Every move you may remove one pearl either from the hanging end (“H”) or from the table end (“T”). After an “H”, you must slide the string so that exactly m pearls hang again (one more pearl moves from table to hanging, but is not stolen). After each move (both H and T), the hanging-weight Wh must satisfy  
 Wh ≤ k · Wt  
where Wt is the total weight on the table and k is a given friction coefficient. Maximize the total stolen value, and output the number of moves, that total value, and one valid sequence of ‘H’/‘T’ moves achieving it.

2. Key observations  
•  Any “T” move only decreases Wt (hanging weight Wh is unchanged), so it makes the inequality Wh ≤ k·Wt harder to satisfy.  
•  Any “H” move decreases Wh (you steal the last hanging pearl) but also shifts one pearl from table to hanging, so net Wh may go up or down. However, “H” does not change the number of pearls on the table beyond that one shift.  
•  If you ever do a “T” before finishing all your planned “H” moves, you reduce Wt early and make remaining “H” moves strictly harder. Therefore in any optimal plan you do all your H moves first (as many as you can safely), and then do T moves.  
•  After you choose t = number of H’s (0 ≤ t ≤ n–m), you can check if they are safe by computing new Wh and Wt via prefix sums. Then you choose as many T’s as possible (say y) by binary-searching the largest y for which, after removing y from the front, the condition Wh ≤ k·(new Wt) still holds.

3. Full solution approach  
a. Read n, m, k and arrays w[0..n–1], c[0..n–1].  
b. Build two prefix-sum arrays prefW[i] = w[0]+…+w[i], prefC[i] = c[0]+…+c[i]. This lets you get weight or value sums on any interval in O(1).  
c. Maintain scoreH = 0, which will be the sum of values of the last t stolen pearls after t “H” moves. We will increase t from 0 upward and add c[n–1–(t–1)] each time.  
d. For t from 0 to n–m (inclusive):  
   1. Let remaining length L = n – t. If L < m, break.  
   2. Compute Wh = sum of w[L–m..L–1], and Wt = sum of w[0..L–m–1].  
   3. If Wh > k·Wt, break the loop (further t will only make Wt smaller).  
   4. Binary-search y in [0..L–m] to find the largest y such that  
        Wh ≤ k · sum of w[y..L–m–1].  
      This sum is the table weight after y “T” moves.  
   5. The total stolen value is scoreH + sum of c[0..y–1]. If this is better than the best so far, record (t,y) and the new best total.  
   6. Increase scoreH by c[n–1–t] to prepare for the next t+1.  
e. At the end, the best plan is to do t ‘H’ moves followed by y ‘T’ moves, where (t,y) gave the maximum total value. If the best total is zero, output “0 0”. Otherwise output “t+y best_total” and then a string of t ‘H’s then y ‘T’s.

Time complexity: O(n log n). Memory: O(n).

4. C++ implementation with detailed comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Fast I/O
static const int MAXN = 200000;
int n, m, k;
int w[MAXN], c[MAXN];
long long prefW[MAXN], prefC[MAXN];

inline long long getWeight(int l, int r) {
    if (l > r) return 0;
    return prefW[r] - (l ? prefW[l-1] : 0LL);
}
inline long long getCost(int l, int r) {
    if (l > r) return 0;
    return prefC[r] - (l ? prefC[l-1] : 0LL);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Read input
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> c[i];
        prefW[i] = w[i] + (i ? prefW[i-1] : 0);
        prefC[i] = c[i] + (i ? prefC[i-1] : 0);
    }

    long long bestTotal = 0;
    int bestT = 0, bestY = 0;
    long long scoreH = 0; // sum of values stolen by H moves so far

    // Try t = 0 .. up to n-m H moves
    for (int t = 0; t <= n - m; t++) {
        int L = n - t;            // remaining string length
        if (L < m) break;

        // Compute current hanging weight and table weight
        long long Wh = getWeight(L - m, L - 1);
        long long Wt = getWeight(0, L - m - 1);

        // If unstable, no more t will work
        if (Wh > (long long)k * Wt) {
            break;
        }

        // Binary-search max y in [0..L-m] so that Wh <= k * Wt_after_T
        int low = 0, high = L - m, bestY_for_t = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            long long Wt_after = getWeight(mid, L - m - 1);
            if (Wh <= (long long)k * Wt_after) {
                bestY_for_t = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // Total stolen = sum of last t pearls' values + first bestY_for_t pearls' values
        long long totalValue = scoreH + getCost(0, bestY_for_t - 1);
        if (totalValue > bestTotal) {
            bestTotal = totalValue;
            bestT = t;
            bestY = bestY_for_t;
        }

        // Prepare scoreH for the next t+1 by adding the next H-pearl's value
        if (t < n) {
            scoreH += c[n - 1 - t];
        }
    }

    // Output result
    if (bestTotal == 0) {
        cout << "0 0\n";
        return 0;
    }
    cout << (bestT + bestY) << " " << bestTotal << "\n";
    // t 'H's then y 'T's
    for (int i = 0; i < bestT; i++) cout << 'H';
    for (int i = 0; i < bestY; i++) cout << 'T';
    cout << "\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys
data = sys.stdin.read().split()
if not data:
    print("0 0")
    sys.exit(0)

it = iter(data)
n = int(next(it))
m = int(next(it))
k = int(next(it))

# Read weights and values
w = [0]*n
c = [0]*n
for i in range(n):
    w[i] = int(next(it))
    c[i] = int(next(it))

# Build prefix sums for weights and values
prefW = [0]*n
prefC = [0]*n
prefW[0] = w[0]
prefC[0] = c[0]
for i in range(1,n):
    prefW[i] = prefW[i-1] + w[i]
    prefC[i] = prefC[i-1] + c[i]

def getW(l, r):
    if l > r: return 0
    return prefW[r] - (prefW[l-1] if l>0 else 0)

def getC(l, r):
    if l > r: return 0
    return prefC[r] - (prefC[l-1] if l>0 else 0)

bestTotal = 0
bestT = bestY = 0
scoreH = 0  # sum of values stolen by H so far

# Try t = 0 .. up to n-m H moves
for t in range(n - m + 1):
    L = n - t
    if L < m:
        break

    # Hanging weight and table weight after t H moves
    Wh = getW(L-m, L-1)
    Wt = getW(0, L-m-1)
    # If unstable, further t will also fail
    if Wh > k * Wt:
        break

    # Binary-search the max y in [0..L-m] so that Wh <= k * Wt_after_y_Ts
    lo, hi = 0, L - m
    y_ok = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if Wh <= k * getW(mid, L - m - 1):
            y_ok = mid
            lo = mid + 1
        else:
            hi = mid - 1

    totalValue = scoreH + getC(0, y_ok - 1)
    if totalValue > bestTotal:
        bestTotal = totalValue
        bestT = t
        bestY = y_ok

    # Add the next hanging-pearl's value for t+1
    if t < n:
        scoreH += c[n-1-t]

# Print the result
if bestTotal == 0:
    print("0 0")
else:
    p = bestT + bestY
    print(p, bestTotal)
    print('H'*bestT + 'T'*bestY)
```