2019 NHSPC north1 pB

#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define X first
#define Y second
#define Push push_back
#define ALL(x) x.begin(), x.end()

using lli = long long;
using pll = pair<lli, lli>;
using Double = long double;
template<typename T>
using Vector = vector<vector<T>>;
template<typename T>
using prior = priority_queue<T>;

int main() {
    IOS;
    int n;
    cin >> n;

    Vector<int> mp(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            cin >> mp[i][j];
        }
    }

    Vector<pll> dp(n + 1, vector<pll>(n + 1, {0, 0}));
    dp[1][1].X = mp[1][1];

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i][j].X = max(dp[i][j - 1].X, dp[i - 1][j].X) + mp[i][j];
            if (dp[i][j - 1].X > dp[i - 1][j].X) dp[i][j].Y = 0; // east
            else dp[i][j].Y = 1; // south
        }
    }

    string walk = "E";
    int x = n, y = n;
    while (x > 1 or y > 1) {
        if (dp[x][y].Y) {
            walk += 'S';
            --x;
        }
        else {
            walk += 'E';
            --y;
        }
    }

    walk += "E";
    reverse(ALL(walk));

    cout << walk << "\n";
    cout << dp[n][n].X << "\n";

    return 0;
}