#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 5e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);

int n, m;
LL arr[maxn];
struct Tree{
    int l, r;
    LL maxv, lsum, rsum, sum;
}t[maxn<<2];

inline LL max(LL a, LL b, LL c){
    return max(a, max(b, c));
}
inline void pushup(int cur){
    t[cur].sum = t[cur<<1].sum + t[cur<<1|1].sum;
    t[cur].lsum = max(t[cur<<1].lsum, t[cur<<1].sum + t[cur<<1|1].lsum);
    t[cur].rsum = max(t[cur<<1|1].rsum, t[cur<<1].rsum + t[cur<<1|1].sum);
    t[cur].maxv = max(t[cur<<1].maxv, t[cur<<1|1].maxv, t[cur<<1].rsum + t[cur<<1|1].lsum);
}
void build(int l, int r, int cur){
    t[cur].l = l; t[cur].r = r;
    t[cur].maxv = t[cur].lsum = t[cur].rsum = -inf;
    t[cur].sum = 0;
    if(l == r){
        t[cur].maxv = t[cur].lsum = t[cur].rsum = t[cur].sum = 1LL * arr[l];
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, cur<<1);
    build(mid + 1, r, cur<<1|1);
    pushup(cur);
}
void change(int pos, int x, int cur){
    if(t[cur].l == t[cur].r){
        if(t[cur].l == pos) t[cur].maxv = t[cur].lsum = t[cur].rsum = t[cur].sum = x;
        return;
    }
    int mid = t[cur].l + t[cur].r >> 1;
    if(pos <= mid) change(pos, x, cur<<1);
    else change(pos, x, cur<<1|1);
    pushup(cur);
}
Tree query(int l , int r, int cur){
    Tree a, b, c;
    if(l <= t[cur].l && t[cur].r <= r){
        return t[cur];
    }
    int mid = t[cur].l + t[cur].r >> 1;
    a.sum = a.lsum = a.rsum = a.maxv = -inf - 1;
    b.sum = b.lsum = b.rsum = b.maxv = -inf - 1;
    c.lsum = c.rsum = c.maxv = -inf - 1; c.sum = 0;
    if(l <= mid){
        a = query(l, r, cur << 1);
        c.sum += a.sum;
    }
    if(mid < r){
        b = query(l, r, cur<<1|1);
        c.sum += b.sum;
    }
    c.lsum = max(a.lsum, a.sum + b.lsum);
    c.rsum = max(b.rsum, a.rsum + b.sum);
    c.maxv = max(a.maxv, max(b.maxv, a.rsum + b.lsum));
    return c;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &arr[i]);
    }
    build(1, n, 1);
    while(m--){
        int k, l, r;
        scanf("%d %d %d", &k, &l, &r);
        if(k == 1){
            printf("%lld\n", query(min(l, r), max(l, r), 1).maxv);
        }
        else{
            change(l, r, 1);
        }
    }
    getchar(); getchar();
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 4e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int n, m, e, ans, f[maxn];
struct Node{
    int l, r, val;
    bool operator <(Node a){
        return r < a.r;
    }
}arr[maxn];
struct Tree{
    int l, r, minv;
}tree[maxn];

inline void pushup(int cur){
    tree[cur].minv = min(tree[cur<<1].minv, tree[cur<<1|1].minv);
}
void build(int l, int r, int cur){
    tree[cur].l = l; tree[cur].r = r;
    if(l == r){
        tree[cur].minv = l == m - 1 ? 0 : inf;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, cur<<1);
    build(mid + 1, r, cur<<1|1);
    pushup(cur);
}
void modify(int pos, int x, int cur)
{
    if(tree[cur].l == tree[cur].r){
        tree[cur].minv = x;
        return;
    }
    int mid = tree[cur].l + tree[cur].r >> 1;
    if(pos <= mid)    modify(pos, x, cur << 1);
    else modify(pos, x, cur<<1|1);
    pushup(cur);
}
void query(int l, int r, int cur)
{
    if(l <= tree[cur].l && tree[cur].r <= r){
        ans = min(ans, tree[cur].minv);
        return;
    }
    int mid = (tree[cur].l + tree[cur].r) >> 1;
    if(l <= mid) query(l,r,cur<<1);
    if(mid < r)  query(l,r,cur<<1|1);
}

int main()
{
    scanf("%d %d %d", &n, &m, &e); m += 1; e += 1;
    for(int i = 1; i <= n; ++i){
        scanf("%d %d %d", &arr[i].l, &arr[i].r, &arr[i].val);
        arr[i].l++; arr[i].r++;
    }
    sort(arr + 1, arr + n + 1);
    memset(f, inf, sizeof(f));
    build(m - 1, e, 1);
    int res = inf;
    for(int i = 1; i <= n; ++i){
        ans = inf;
        query(arr[i].l - 1, min(arr[i].r - 1, e), 1);
        f[arr[i].r] = min(f[arr[i].r], ans + arr[i].val);
        modify(arr[i].r, f[arr[i].r], 1);
        if(arr[i].r >= e)   res = min(res, f[arr[i].r]);
    }
    printf("%d\n", res == inf ? -1 : res);
    getchar(); getchar();
}

#include <bits/stdc++.h>

using namespace std;
const int maxn = 4e6 + 10;
const int inf = 0x3f3f3f3f;

struct node{
    int l, r, minv;
}tree[maxn];
struct Node{
    int l, r;
    bool operator <(Node a){
        return r < a.r;
    }
}arr[maxn];
int n, t, f[maxn];
int ans;

inline void pushup(int cur){
    tree[cur].minv = min(tree[cur<<1].minv, tree[cur<<1|1].minv);
}
void build(int l, int r, int cur){
    tree[cur].l = l; tree[cur].r = r;
    if(l == r){
        tree[cur].minv = l == 0 ? 0 : inf;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, cur<<1);
    build(mid + 1, r, cur<<1|1);
    pushup(cur);
}
void modify(int pos, int x, int cur)
{
    if(tree[cur].l == tree[cur].r){
        if(tree[cur].l == pos)  tree[cur].minv = x;
        return;
    }
    int mid = tree[cur].l + tree[cur].r >> 1;
    if(pos <= mid)  modify(pos, x, cur<<1);
    else modify(pos, x, cur<<1|1);
    pushup(cur);
}
void query(int l, int r, int cur){
    if(l <= tree[cur].l && tree[cur].r <= r){
        ans = min(ans, tree[cur].minv);
        return;
    }
    int mid = tree[cur].l + tree[cur].r >> 1;
    if(l <= mid)    query(l, r, cur<<1);
    if(mid < r) query(l, r, cur<<1|1);
}

int main()
{
    scanf("%d %d", &n, &t);
    build(0, t, 1);
    for(int i = 1; i <= n; ++i){
        scanf("%d %d", &arr[i].l, &arr[i].r);
    }
    sort(arr + 1, arr + n + 1);
    memset(f, inf, sizeof(f));
    int res = inf;
    for(int i = 1; i <= n; ++i){
        ans = inf;
        query(arr[i].l - 1, arr[i].r - 1, 1);
        f[arr[i].r] = min(f[arr[i].r], ans + 1);
        modify(arr[i].r, f[arr[i].r], 1);
        if(arr[i].r >= t)   res = min(res, f[arr[i].r]);
    }
    printf("%d\n", res == inf ? -1 : res);
    getchar(); getchar();
}

#include <bits/stdc++.h>
#define mp make_pair

using namespace std;
typedef long long LL;
const LL inf = 1e15;
const int maxn = 1e5 + 10;

typedef pair<LL, LL> pll;
set<pll> s;
LL n, arr[maxn];

int main()
{
    s.insert(mp(-inf, 0));
    s.insert(mp(inf, 0));
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &arr[i]);
        if(i == 1)  s.insert(mp(arr[i], i));
        else{
            auto maxv = s.upper_bound(mp(arr[i], 0));
            auto minv = maxv; minv--;
            LL tmin = arr[i] - minv->first, tmax = maxv->first - arr[i];
            if(tmin <= tmax)    printf("%lld %lld\n", tmin, minv->second);
            else printf("%lld %lld\n", tmax, maxv->second);
            s.insert(mp(arr[i], i));
        }
    }
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 1 << 11;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1.0);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int n, m;
int f[2][maxn][maxn], g[110];
char s[110][11];
vector<int> state;

bool ok(int x){
    for(int i = 0; 1 << i <= x; ++i){
        if((x & 1 << i) && ((x & 1 << i + 1) || (x & 1 << i + 2))) return 0;
    }
    return 1;
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i){
        scanf("%s", s[i]);
        for(int j = 0; j < m; ++j){
            if(s[i][j] == 'P')  continue;
            g[i] += 1 << j;
        }
    }
    for(int i = 0; i < 1 << m; ++i){    //打表， 将符合条件的状态存起来
        if(ok(i))   state.push_back(i);
    }
    int len = state.size();
    for(int i = 0; i <= n + 1; ++i){    //阶段： 枚举到哪一行了
        for(int j = 0; j < len; ++j){    //状态：上山一行的状态
            for(int k = 0; k < len; ++k){    //状态：上一行的状态
               for(int u = 0; u < len; ++u){    //状态：这一行的状态, 顺序可以乱
                    int now = state[u], pre = state[k], ppre = state[j];
                    if((now & pre) || (now & ppre) || (pre & ppre)) continue;
                    if(g[i] & now) continue;
                    f[i&1][now][pre] = max(f[i&1][now][pre], f[i-1&1][pre][ppre] + __builtin_popcount(now));
                    //决策， 这个状态可以从上一行的状态转移而来
                }
            }
        }
    }
    printf("%d\n", f[n+1&1][0][0]);
    system("pause");
}

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 12;

LL f[N][1<<N];
int m, n, st[1<<N];
vector<int> v[1<<N];

int main()
{
    while(~scanf("%d %d", &m, &n), m && n){     // m * n
        for(int i = 0; i < 1 << n; ++i){        //判断这个数每两个1之间0的个数是否为偶数个
            int cnt = 0, ok = 1;
            for(int j = 0; j < n; ++j){
                if((i & 1 << j)){
                    if(cnt & 1) ok = 0;
                    else cnt = 0;
                }
                else cnt ^= 1;
                if(ok == 0) break;
            }
            if(cnt & 1) ok = 0;
            st[i] = ok;
        }
        for(int i = 0; i < 1 << n; ++i){        //预处理出每个状态可以转移的合理状态
            v[i].clear();
            for(int j = 0; j < 1 << n; ++j){
                if((i & j) == 0 && st[i|j])   v[i].push_back(j);
            }
        }
        memset(f, 0 ,sizeof(f));
        f[0][0] = 1;
        for(int i = 1; i <= m; ++i){
            for(int j = 0; j < 1 << n; ++j){
                for(auto k : v[j]){
                    f[i][j] += f[i-1][k];
                }
            }
        }
        printf("%lld\n", f[m][0]);
    }
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 2e6 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int n, arr[maxn];
int f[maxn], que[maxn];
int tail, head = 1;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
        arr[i+n] = arr[i];
    }
    que[++tail] = 1;
    int ans = arr[2] + arr[1] + 1;
    for(int  i = 2; i <= 2 * n; ++i){
        ans = max(ans, arr[que[head]] - que[head] + arr[i] + i);
        while(head <= tail && arr[i] - i > arr[que[tail]] - que[tail]) tail--;
        que[++tail] = i;
        if(que[tail] - que[head] >= n / 2)  head++;
    }
    printf("%d\n", ans);
    system("pause");
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 3840;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int arr[maxn], n, b;
int f[2][maxn][2], u[maxn];     //滚动数组优化

int main()
{
    scanf("%d %d", &n, &b);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &u[i]);
    }
    memset(f, -inf, sizeof(f));
    f[1&1][1][0] = f[1&1][1][1] = 0;
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= i; ++j){
            f[i&1][j][0] = max(f[(i-1)&1][j][0], f[(i-1)&1][j][1]);
            if(j > 1) f[i&1][j][1] = max(f[(i-1)&1][j-1][0], f[(i-1)&1][j-1][1] + u[i]);
            else f[i&1][j][1] = 0;
        }
    }
    int ans = max(f[n&1][b][0], f[n&1][b][1]);
    memset(f, -inf, sizeof(f));
    f[1&1][1][1] = u[1];
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= i; ++j){
            f[i&1][j][0] = max(f[(i-1)&1][j][0], f[(i-1)&1][j][1]);
            f[i&1][j][1] = max(f[(i-1)&1][j-1][0], f[(i-1)&1][j-1][1] + u[i]);
        }
    }
    ans = max(ans, f[n&1][b][1]);
    printf("%d\n", ans);
    system("pause");
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

struct edge{
    int nex, to, val;
}Edge[maxn<<1];
int head[maxn], tot;
int n, de[maxn], f[maxn], dis[maxn];

inline void init()
{
    tot = 0;
    for(int i = 1; i <= n; ++i){
        dis[i] = de[i] = 0;
        head[i] = -1;
    }
}
inline void add(int from, int to, int val){
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    Edge[tot].val = val;
    head[from] = tot;
}
void dp(int u, int fa)         //树形dp， 自下而上
{
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(fa == v) continue;
        dp(v, u);
        if(de[v] == 1)  dis[u] += Edge[i].val;          //一定要注意边界条件！
        else dis[u] += min(Edge[i].val, dis[v]);
    }
}   
void dfs(int u, int fa)         //换根， 每个点O(1)换根, n割点O(n)
{
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        if(fa == v) continue;                           //找到新根与原来的dis之间的关系
        if(de[u] == 1)  f[v] = Edge[i].val + dis[v];
        else f[v] = dis[v] + min(Edge[i].val, f[u] - min(Edge[i].val, dis[v]));
        dfs(v, u);
    }
}

int main()
{
    int t; scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        init();
        for(int i = 1; i < n; ++i){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            add(a, b, c), add(b, a, c);
            de[a]++, de[b]++;
        }
        int rt = 1;             //随便选一个点作为根节点做一下树形dp
        dp(rt, -1);    f[1] = dis[1];
        dfs(rt, -1);            //再利用刚刚那个根堆每个点换一下根
        int ans = 0;
        for(int i = 1; i <= n; ++i){
            ans = max(ans, f[i]);
        }
        printf("%d\n", ans);
    }
    system("pause");
}

#include <bits/stdc++.h>
#define debug(x) cout << #x << " = " << x << endl; 

using namespace std;
typedef long long LL;
const int maxn = 330;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6, pi = acos(-1);
int gcd(int a,int b)    { return b == 0 ? a : gcd(b, a % b); }

int n, m;
int f[maxn][maxn];      //f[i][j]表示以i为根的子树中，空间为j的最大价值
struct node{
    int nex, to;
}Edge[maxn];
int tot, head[maxn];
int w[maxn], v[maxn];

inline void add(int from, int to)
{
    Edge[++tot].to = to;
    Edge[tot].nex = head[from];
    head[from] = tot;
}
void dfs(int u)
{
    for(int i = w[u]; i <= m; ++i)    f[u][i] = v[u];
    for(int i = head[u]; i != -1; i = Edge[i].nex){
        int v = Edge[i].to;
        dfs(v);
        for(int j = m; j >= w[u]; --j){
            for(int k = 0; k <= j - w[u]; ++k){
                f[u][j] = max(f[u][j], f[u][j-k] + f[v][k]);
            }
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i){
        int x, y;
        scanf("%d %d", &x, &y);
        v[i] = y;  
        add(x, i);
    }
    for(int i = 1; i <= n; ++i) w[i] = 1;
    dfs(0);
    printf("%d\n", f[0][m]);
    system("pause");
}