#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;
int n;
int x, y, xx, yy;
PII q[N];

int dist(int x, int y, int xx, int yy) {
    int dx = x - xx;
    int dy = y - yy;
    return dx * dx + dy * dy;
}

bool cmp(PII a, PII b) {
    return dist(a.x, a.y, x, y) > dist(b.x, b.y, x, y);
}

int main()
{
    cin >> x >> y >> xx >> yy;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &q[i].x, &q[i].y);
    sort(q + 1, q + n + 1, cmp);

    int len = 0;
    int res = dist(q[1].x, q[1].y, x, y);
    for (int i = 1; i <= n; i ++ ) {
        len = max(len, dist(q[i].x, q[i].y, xx, yy));
        if (i + 1 <= n) res = min(res, len + dist(q[i + 1].x, q[i + 1].y, x, y));
    }
    res = min(res, len);
    cout << res << endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int n;
int w[N], l[N], r[N], s[N];
int ans;

int dfs(int u) {
    if (!u) return 0;

    s[u] = dfs(l[u]) + dfs(r[u]) + 1;
    return s[u];
}

bool check(int a, int b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    if (w[a] != w[b]) return false;
    return check(l[a], r[b]) && check(r[a], l[b]);
}

void yxc(int u) {
    if (!u) return;
    if (s[l[u]] == s[r[u]]) 
        if (check(l[u], r[u])) {
            ans = max(ans, s[u]);
            return;
        }
    yxc(l[u]);
    yxc(r[u]);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d%d", &l[i], &r[i]);
        if (l[i] == -1) l[i] = 0;
        if (r[i] == -1) r[i] = 0;
    }

    dfs(1);
    yxc(1);

    printf("%d", ans);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int n;
int w[N], l[N], r[N], s[N];
int ans;

int dfs(int u) {
    if (!u) return 0;

    s[u] = dfs(l[u]) + dfs(r[u]) + 1;
    return s[u];
}

bool check(int a, int b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    if (w[a] != w[b]) return false;
    return check(l[a], r[b]) && check(r[a], l[b]);
}

void yxc(int u) {
    if (!u) return;
    if (s[l[u]] == s[r[u]]) 
        if (check(l[u], r[u])) {
            ans = max(ans, s[u]);
            return;
        }
    yxc(l[u]);
    yxc(r[u]);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d%d", &l[i], &r[i]);
        if (l[i] == -1) l[i] = 0;
        if (r[i] == -1) r[i] = 0;
    }

    dfs(1);
    yxc(1);

    printf("%d", ans);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, inf = 0x3f3f3f3f;
int n, m;
int w[N][N];
long long f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &w[i][j]);
    }

    memset(f, -0x3f, sizeof f);
    f[1][0] = 0;

    for (int j = 1; j <= m; j ++ ) {
        long long s = -inf;
        for (int i = 1; i <= n; i ++ ) {
            s = max(s, f[i][j - 1]) + w[i][j];
            f[i][j] = max(f[i][j], s);
        }
        s = -inf;
        for (int i = n; i; i -- ) {
            s = max(s, f[i][j - 1]) + w[i][j];
            f[i][j] = max(f[i][j], s);
        }
    }

    printf("%lld", f[n][m]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500010;
int n, d, k;
int x[N], w[N];
ll f[N];
int q[N];

bool check(int mid) {
    int l = max(1, d - mid), r = d + mid;
    ll res = 0;
    int hh = 0, tt = -1;
    memset(f, -0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1, j = 0, k = 0; i <= n; i ++ ) {
        while (x[i] - x[k] >= l) {
            while (hh <= tt && f[q[tt]] <= f[k]) tt --;
            q[ ++ tt] = k ++;
        }
        while (x[i] - x[j] > r) j ++;
        while (hh <= tt && q[hh] < j) hh ++;

        if (hh <= tt) f[i] = f[q[hh]] + w[i];
        res = max(res, f[i]);
    }

    return res >= k;
}

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &x[i], &w[i]);

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (!check(r)) r = -1;
    printf("%d", r);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 500010;
int n, d, k;
int x[N], w[N];
ll f[N];
int q[N];

bool check(int mid) {
    int l = max(1, d - mid), r = d + mid;
    ll res = 0;
    int hh = 0, tt = -1;
    memset(f, -0x3f, sizeof f);
    f[0] = 0;

    for (int i = 1, j = 0, k = 0; i <= n; i ++ ) {
        while (x[i] - x[k] >= l) {
            while (hh <= tt && f[q[tt]] <= f[k]) tt --;
            q[ ++ tt] = k ++;
        }
        while (x[i] - x[j] > r) j ++;
        while (hh <= tt && q[hh] < j) hh ++;

        if (hh <= tt) f[i] = f[q[hh]] + w[i];
        res = max(res, f[i]);
    }

    return res >= k;
}

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &x[i], &w[i]);

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (!check(r)) r = -1;
    printf("%d", r);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 110;
int n, m;
int g[N][N];
struct node{
    int x, y, z;
};
int dist[N][N][2];
bool st[N][N][2];

int spfa() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    memset(dist, 0x3f, sizeof dist);
    queue<node> q;
    dist[1][1][g[1][1]] = 0;
    q.push({1, 1, g[1][1]});

    while (q.size()) {
        node t = q.front();
        q.pop();

        st[t.x][t.y][t.y] = false;
        for (int i = 0; i < 4; i ++ ) {
            int x = t.x + dx[i], y = t.y + dy[i];

            if (x < 1 || x > n || y < 1 || y > n) continue;
            int c1 = g[t.x][t.y], c2 = g[x][y], d = 2, z = c2;

            if (c2 != -1) {
                d = t.z == c2 ? 0 : 1;
                //cout << d << endl;
                if (dist[x][y][z] > dist[t.x][t.y][t.z] + d) {
                    dist[x][y][z] = dist[t.x][t.y][t.z] + d;
                    if (!st[x][y][z]) {
                        q.push({x, y, z});
                        st[x][y][z] = true;
                    }
                }
            }
            else if (c1 != -1) {
                for (z = 0; z < 2; z ++ ) {
                    if (z != c1) d ++;
                    if (dist[x][y][z] > dist[t.x][t.y][t.z] + d) {
                        dist[x][y][z] = dist[t.x][t.y][t.z] + d;
                        if (!st[x][y][z]) {
                            q.push({x, y, z});
                            st[x][y][z] = true;
                        }
                    }
                    if (z != c1) d --;
                }
            }
            else continue;
        }
    }
    int res = min(dist[n][n][0], dist[n][n][1]);
    if (res == 0x3f3f3f3f) res = -1;
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, -1, sizeof g);
    while (m -- ) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = c;
    }

    cout << spfa() << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15010, M = 40010;
int n, m;
int cnt[N];
int a[N], b[N], c[N], d[N], x[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        cin >> x[i];
        cnt[x[i]] ++;
    }

    for (int t = 1; 9 * t + 2 <= n; t ++ ) {
        int sum = 0;
        for (int D = 9 * t + 2; D <= n; D ++ ) {
            int B = D - 7 * t - 1;
            int A = B - t * 2;
            int C = D - t;
            sum += cnt[A] * cnt[B];
            c[C] += sum * cnt[D];
            d[D] += sum * cnt[C];
        }
        sum = 0;
        for (int A = n - 9 * t - 1; A; A -- ) {
            int B = A + 2 * t;
            int C = B + 6 * t + 1;
            int D = C + t;
            sum += cnt[C] * cnt[D];
            a[A] += sum * cnt[B];
            b[B] += sum * cnt[A];
        }
    }
    for (int i = 1; i <= m; i ++ )
        printf("%d %d %d %d\n", a[x[i]], b[x[i]], c[x[i]], d[x[i]]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15010, M = 40010;
int n, m;
int cnt[N];
int a[N], b[N], c[N], d[N], x[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        cin >> x[i];
        cnt[x[i]] ++;
    }

    for (int t = 1; 9 * t + 2 <= n; t ++ ) {
        int sum = 0;
        for (int D = 9 * t + 2; D <= n; D ++ ) {
            int B = D - 7 * t - 1;
            int A = B - t * 2;
            int C = D - t;
            sum += cnt[A] * cnt[B];
            c[C] += sum * cnt[D];
            d[D] += sum * cnt[C];
        }
        sum = 0;
        for (int A = n - 9 * t - 1; A; A -- ) {
            int B = A + 2 * t;
            int C = B + 6 * t + 1;
            int D = C + t;
            sum += cnt[C] * cnt[D];
            a[A] += sum * cnt[B];
            b[B] += sum * cnt[A];
        }
    }
    for (int i = 1; i <= m; i ++ )
        printf("%d %d %d %d\n", a[x[i]], b[x[i]], c[x[i]], d[x[i]]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;
int t, n, m;
int w[N][N];
int f[M];

int main()
{
    cin >> t >> n >> m;
    for (int i = 1; i <= t; i ++ ) 
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    for (int i = 1; i <= t; i ++ ) {
        memset(f, 0, sizeof f);
        for (int j = 1; j <= n; j ++ )
            for (int k = w[i][j]; k <= m; k ++ )
                f[k] = max(f[k], f[k - w[i][j]] + w[i + 1][j] - w[i][j]);
        m += f[m];
    }
    cout << m << endl;
    return 0;
}