<|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.
- 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 safety 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 the array a[0..n–1] of (weight, value) pairs.
b. Build two prefix-sum arrays pref_w[i] = w[0]+…+w[i] and pref_score[i] = c[0]+…+c[i], enabling range queries get_weight(l,r) and get_score(l,r) in O(1).
c. Iterate len from n down to m+1 (len is the remaining string length, so n–len H's have been taken). Maintain `add` = sum of values of pearls taken from the right so far.
d. For each len:
   1. Compute hanging weight = get_weight(len–m, len–1) and table weight = get_weight(0, len–m–1).
   2. If hanging weight > k × table weight, break (further len reductions only shrink the table).
   3. Binary-search the largest left cut ans_pos in [0..len–m–1] such that get_weight(ans_pos, len–m–1) × k ≥ hanging weight. Score from T's = get_score(0, ans_pos–1).
   4. Total = get_score_from_left(len) + add. If better than best, record ans and best_len.
   5. Add a[len–1].second to `add` for the next iteration.
e. Reconstruct: append (n–best_len) 'H' characters, then greedily append 'T' characters from the left while balance holds.

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

4. C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, k;
vector<pair<int, int>> a;

void read() {
    cin >> n >> m >> k;
    a.resize(n);
    cin >> a;
}

void solve() {
    // Pearls 1..n with prefix sums over weight and price. Taking a hanging
    // pearl (H) drops the rightmost remaining pearl; taking a table pearl (T)
    // drops the leftmost remaining one. After all H moves the remaining pearls
    // are a prefix 1..len, and the hanging part is the last m of them; balance
    // requires weight(len-m..len-1) <= k * weight(remaining table pearls).
    //
    // We iterate len from n down to m+1, i.e. over the number of H pearls
    // taken (their prices accumulate in `add`). For each len the hanging
    // weight is fixed, so the most table pearls we may strip from the left is
    // monotone: binary search the largest left cut still keeping balance and
    // add the price of those table pearls. We keep the (len, total) giving the
    // best money.
    //
    // Finally we reconstruct: H characters for every pearl taken from the
    // right, then T characters for table pearls peeled from the left while the
    // balance condition still holds.

    vector<int> pref_w(n), pref_score(n);
    for(int i = 0; i < n; i++) {
        pref_w[i] = a[i].first;
        pref_score[i] = a[i].second;
        if(i > 0) {
            pref_w[i] += pref_w[i - 1];
            pref_score[i] += pref_score[i - 1];
        }
    }

    auto get_weight = [&](int l, int r) -> int {
        if(l > r) {
            return 0;
        }
        return pref_w[r] - (l > 0 ? pref_w[l - 1] : 0);
    };

    auto get_score = [&](int l, int r) -> int {
        if(l > r) {
            return 0;
        }
        return pref_score[r] - (l > 0 ? pref_score[l - 1] : 0);
    };

    auto get_score_from_left = [&](int len) -> int {
        int low = 0, high = len - m - 1, ans_pos = -1;
        int weight_hanging = get_weight(len - m, len - 1);
        while(low <= high) {
            int mid = (low + high) / 2;
            if(get_weight(mid, len - m - 1) * k >= weight_hanging) {
                ans_pos = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        assert(ans_pos != -1);
        return get_score(0, ans_pos - 1);
    };

    int ans = 0, add = 0, best_len = 0;
    for(int len = n; len > m; len--) {
        if(get_weight(len - m, len - 1) > k * get_weight(0, len - m - 1)) {
            break;
        }

        int new_score = get_score_from_left(len) + add;
        if(new_score > ans) {
            ans = new_score;
            best_len = len;
        }

        add += a[len - 1].second;
    }

    if(ans == 0) {
        cout << 0 << ' ' << 0 << '\n';
        return;
    }

    string ans_str;
    for(int i = best_len; i < n; i++) {
        ans_str.push_back('H');
    }

    for(int l = 0; l < best_len; l++) {
        if(get_weight(best_len - m, best_len - 1) >
           k * get_weight(l + 1, best_len - m - 1)) {
            break;
        }

        ans_str.push_back('T');
    }

    cout << ans_str.size() << ' ' << ans << '\n';
    cout << ans_str << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation
```python
import sys
import threading
def main():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    k = int(next(it))
    w = [0]*n
    c = [0]*n
    for i in range(n):
        w[i] = int(next(it))
        c[i] = int(next(it))

    # Build prefix sums
    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]

    # Helpers: sum of w[l..r], sum of c[l..r]
    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)

    best_total = 0
    best_x = 0  # number of H's
    best_y = 0  # number of T's

    scoreH = 0  # cumulative sum of H-values stolen so far
    # Try x = 0 .. up to n-m H-operations
    for x in range(0, n-m+1):
        L = n - x       # length of the remaining string
        if L < m:
            break

        # compute weight of hanging and table
        W_hang = getW(L-m, L-1)
        W_table = getW(0, L-m-1)

        # safety check for the last H we did
        if W_hang > k * W_table:
            break

        # Binary search maximum y in [0..L-m] such that
        # getW(y, L-m-1)*k >= W_hang
        lo, hi = 0, L-m
        best_mid = 0
        while lo <= hi:
            mid = (lo + hi)//2
            if getW(mid, L-m-1) * k >= W_hang:
                best_mid = mid
                lo = mid + 1
            else:
                hi = mid - 1
        y = best_mid

        total = scoreH + getC(0, y-1)
        if total > best_total:
            best_total = total
            best_x = x
            best_y = y

        # prepare scoreH for x+1 by adding the next H-pearl's value
        if x < n:
            scoreH += c[n-1-x]

    # print answer
    if best_total == 0:
        print("0 0")
        return
    p = best_x + best_y
    print(p, best_total)
    # x times 'H' then y times 'T'
    print("H"*best_x + "T"*best_y)

if __name__ == "__main__":
    threading.Thread(target=main).start()
```
