2
3
0 2 5
2 0 8
5 8 0
4
0 3 5 4
3 0 2 6
5 2 0 8
4 6 8 0

80
160

Pembahasan Soal A - The Best Team

Untuk kasus terburuk dimana N = 50, banyaknya tim berbeda yang bisa dibentuk adalah nCk(50,3) = 50*49*48 / 1/2/3 = 19600 tim. 19600 tim termasuk angka yang sangat sedikit (dalam 2 detik, komputer juri dapat melakukan lebih dari 10 juta operasi), sehingga kita dapat mengecek nilai kompatibilitas untuk setiap tim yang dapat dibentuk (brute-force).

Untuk implementasinya, bisa dilakukan 3 nested loop (untuk murid pertama, kedua, dan ketiga). Untuk membentuk sebuah tim, ketiga murid ini haruslah orang yang berbeda. Untuk setiap tim yang bisa dibentuk, kita tinggal menyimpan kompatibilitas tertinggi. Berikut adalah contoh implementasinya.

#include <stdio.h>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

int T,N,P[51][51];

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        REP(i,N) REP(j,N) scanf("%d",&P[i][j]);
        int res = 0;
        REP(i,N) REP(j,N) REP(k,N)
            if (i!=j && i!=k && j!=k)
                res >?= P[i][j] * P[j][k] * P[k][i];
        printf("%d\n",res);
    }
}

Problem B - Largest Labeled Common Ancestor

Time Limit: 2s

Given a labeled complete k-ary tree, find the largest labeled common ancestor of two given nodes. In a complete k-ary tree, the node in the tree is labeled sequentially from the left most child to the right most child, level by level. Largest labeled common ancestor of A and B is defined as the largest labeled node in the tree which has both A and B as descendants. A node is a descendant of itself.

For example, given a k-ary tree with k = 3, the largest labeled common ancestor of node 42 and 7 is node 2 (see the picture below).

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case contains three integers K, A and B (2 ≤ K ≤ 100; 1 ≤ A, B ≤ 2,000,000,000).

Output

For each test case, output in a line the largest labeled common ancestor node.

Sample Input Output for Sample Input 4 3 42 7 2 2 6 2 1 105 4 10 13 2 1 1 3

---

Pembahasan Soal B - Largest Labeled Common Ancestor

Misalkan:

  p(N) adalah parent dari node N, dan
  f(A,B) = X, dimana X adalah node dengan label terbesar yang merupakan ancestor dari node A dan B.

Maka bisa dibuktikan bahwa:

  jika A > B, maka f(A,B) = f(p(A),B),
  jika A < B, maka f(A,B) = f(A,p(B)), dan
  jika A = B, maka f(A,B) = X

Apakah ada yang ingin mencoba membuktikan hal ini?

Jika anda bisa membuktikan hal diatas, maka implementasinya akan sangat mudah, seperti dibawah ini.

#include <stdio.h>

#define p(N) ((N-2)/K + 1)

int K;

int f(int A, int B){
    if (A > B) return f(p(A),B);
    if (A < B) return f(A,p(B));
    return A; // A = B = X
}

int main(){
    int T,A,B;
    scanf("%d",&T);
    while (T--){
        scanf("%d %d %d",&K,&A,&B);
        printf("%d\n",f(A,B));
    }
}

2
+a+b
+A+B^+c^

ab
cAB

Pembahasan Soal C - Stack Machine Simulator

Soal ini bisa diselesaikan dengan mengikuti langkah-langkah yang diminta. Penggunaan STL sangat membantu untuk melakukan operasi reverse. Berikut adalah contoh implementasinya.

#include <stdio.h>
#include <string>
#include <algorithm>

using namespace std;

char s[1000];
int T;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%s",s);
        string r = "";
        for (int i=0; s[i]; i++){
            if (s[i]=='+') r += s[++i];
            else reverse(r.begin(),r.end());
        }
        puts(r.c_str());
    }
}

2
2
0 3
-1 5
0 1
4
2 7 -3 9
-1 -5 4 6
-2 -7 8 -3

1
3

Pembahasan Soal D - Sum to Zero

Misalkan kita mempunyai 2 sorted array: B dan C yang masing-masing berisi N bilangan. Untuk mencari index b di array B dan index c di array C dimana B[b] + C[c] = x, dapat dilakukan dalam O(N) operasi. Caranya adalah dengan menelusuri index b secara menaik (dari 0 sampai N-1) dan menelusuri index c secara menurun (dari N-1 sampai 0), atau sebaliknya. Illustrasinya ada di blog Suhendry.

Jika kita bisa memecahkan masalah diatas, maka cara mencari A[a] + B[b] + C[c] = 0 adalah sama dengan cara mencari B[b] + C[c] = -A[a]. Untuk setiap bilangan x di array A, kita cari apakah ada B[b] + C[c] = x. Karena ada N bilangan di array A, total kompleksitasnya adalah O(N^2).

Untuk mencari banyaknya pasangan elemen (b,c) dimana B[b] + C[c] = x, kita bisa menghitung berapa banyak elemen di B yang valuenya adalah B[b] (countB), dan berapa banyak elemen di C yang valuenya adalah C[c] (countC). Maka banyaknya pasangan elemen (b,c) dimana B[b] + C[c] = x adalah countB * countC.

Dibawah ini adalah contoh implementasi O(N^2) untuk problem D.

#include <algorithm>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

int T, N, A[2000], B[2000], C[2000];

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        REP(i,N) scanf("%d",&A[i]);
        REP(i,N) scanf("%d",&B[i]); std::sort(B,B+N);
        REP(i,N) scanf("%d",&C[i]); std::sort(C,C+N);

        long long res = 0;
        REP(a,N){
            int x = -A[a];   // kita ingin B[b] + C[c] == -A[a]
            int b=0, c=N-1;  // cari b dan c dimana B[b] + C[c] == x
            while (b<N && c>=0){
                int countB = 1;
                while (b+1 < N && B[b] == B[b+1]) b++, countB++;
                while (c>=0 && B[b] + C[c] > x) c--;
                if (c<0) break;
                if (B[b] + C[c] == x){
                    int countC = 1;
                    while (c>0 && C[c] == C[c-1]) c--, countC++;
                    res += countB * countC;
                }
                b++;
            }
        }
        printf("%lld\n",res);
    }
}

3
3
4
7

3
18
56700

Pembahasan Soal E - Playing with Boxes

Bagi yang terlalu sering menggunakan top-down approach, soal ini akan menjadi sulit dipecahkan. Misalkan f(N) adalah banyaknya cara kita memisahkan N kotak. Maka banyaknya cara memisahkan kotak-kotak tersebut bisa dihitung secara rekursif:

f(N) = sum(nCk(N-1,i) * f(i+1) * f(N-(i+1)) * (N-2)! / i! / (N-(i+1)-1)!) dimana i = 0..N-1

#include <stdio.h>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

long long nCk(int n, int k){
    long long ret = 1;
    for (int i=1; i<=k; i++)
        ret = ret * (n-i+1) / i;
    return ret;
}

long long fac(int n){
    if (n<=1) return 1;
    return n * fac(n-1);
}

long long f(int N){
    if (N<=2) return 1;
    long long ret = 0;
    REP(i,N-1){
        ret += nCk(N-1,i) * f(i+1) * f(N-(i+1)) * fac(N-2) / fac(i) / fac(N-(i+1)-1);
    }
    return ret;
}

int main(){
    // Generate the first 10 results
    for (int i=1; i<=10; i++)  
        printf("%d = %lld\n",i,f(i));

    /*
    Hasilnya adalah:

    1 = 1
    2 = 1
    3 = 3
    4 = 18
    5 = 180
    6 = 2700
    7 = 56700
    8 = 1587600
    9 = 57153600
    10 = 2571912000
    */
}

Terlihat pola bahwa jawaban untuk f(N) ternyata adalah hasil dari perkalian f(N-1) dengan suatu bilangan. Jika kita telusuri lebih dalam, kita bisa menemukan pola perkalian tersebut. Sehingga kita bisa membuat solusi yang lebih simple dan cepat, seperti berikut ini.

#include <stdio.h>

int T,N,res[100001];

int main(){
    res[1] = 1;
    for (long long i=2,a=1,b=2; i<=100000; i++, a+=b, b++)
        res[i] = res[i-1] * a % 1000000007;

    scanf("%d",&T);
    while (T--){
        scanf("%d",&N);
        printf("%d\n",res[N]);
    }
}

Problem F - Searching in Tree

Time Limit: 8s

Given a rooted tree which contains N nodes numbered from 0 to N-1 with node 0 as the root. Each node has a distinct value assigned to it. You have to write a program that can find the k^th smallest value in the subtree of a given node X_i.

Input

The first line of input contains an integer T (1 ≤ T ≤ 20) the number of cases. Each case begins with two integers N and Q (1 ≤ N ≤ 100,000; 1 ≤ Q ≤ 10,000) denoting the number of nodes and queries respectively. The next line contains N integers V_i (0 ≤ V_i ≤ 2³¹-1) denoting the value assigned to i^th node. The next line contains N integers P_i (0 ≤ P_i < N) denoting the parent of i^th node. Parent of node 0 will be 0. The next Q lines each contains two integers k_i and X_i (1 ≤ k_i ≤ sizeof-subtree; 0 ≤ X_i < N).

Output

For each test case, output "Case #X:" (without quotes) where X is the case number starting with 1. Answer each query of the cases in a separate line.

Sample Input Output for Sample Input 1 8 5 12 6 2 10 3 15 1 7 0 2 0 0 3 3 2 3 1 0 3 0 2 3 1 6 3 3 Case #1: 1 3 7 1 10

Explanation for the 1^st sample input:

---

Pembahasan Soal F - Searching in Tree

Dibawah ini adalah contoh implementasi yang dijelaskan di blog Suhendry. Implementasi dalam C/C++ bisa dilakukan tanpa menggunakan pointer. Untuk membuat node baru, kita tinggal meminta index dari kumpulan node yang bebas. Untuk menghapus node, kita tinggal kembalikan index dari node yang dihapus ke dalam kumpulan node bebas. Catatan: implementasi dibawah ini bukan AVL tree, tetapi tree buatan saya sendiri :P.

Semua queries untuk sub-tree tertentu bisa dikumpulkan terlebih dahulu dan kemudian dijawab sekaligus saat kita membangun tree.

Solusi alternatif menggunakan Segment-tree dijelaskan di blog Eko. Solusi Segment-tree tersebut memerlukan O(N log N) space, sedangkan tree saya hanya membutuhkan O(N) space.

#include <stdio.h>
#include <vector>

using namespace std;

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)
#define H(r) ((r)==-1? 0 : node[r].height)
#define S(r) ((r)==-1? 0 : node[r].size)
#define MAXN 200000 // there can be up to 2 trees of size 100000

struct Node {
    int label;      // this node label (acquired from the input).
    int size;       // the size of this subtree (leaf's size is 1).
    int height;     // the height of this node (leaf's height is 1).
    int L, R;       // the index of the left and right child of this node.
} node[MAXN];

vector<int> fnode;  // free node indices (no pointers needed :)

void update(int r){     // update node r's attributes based on its children
    Node &n = node[r];
    n.size = S(n.L) + S(n.R) + 1;
    n.height = 1 + max(H(n.L), H(n.R));
}

void add(int &root, int label){ // insert a new node with the specified label
    if (root==-1){
        root = fnode.back(); fnode.pop_back();          // take a free node
        node[root] = (Node){ label, 1, 1, -1, -1 };     // fill in the new node
    } else {
        Node &n = node[root];
        if (n.label == label) return; // label already exists, ignore add
        if (label < n.label){
            add(n.L, label);
            if (H(n.L) > H(n.R)+1){ // rotate right
                int t = node[n.L].R;
                node[n.L].R = root, root = n.L, n.L = t;
                update(node[root].R);
            }
        } else if (label > n.label){
            add(n.R, label);
            if (H(n.L)+1 < H(n.R)){ // rotate left
                int t = node[n.R].L;
                node[n.R].L = root, root = n.R, n.R = t;
                update(node[root].L);
            }
        }
        update(root);
    }
}

int kth(int root, int k){
    Node &n = node[root];
    if (S(n.L) > k) return kth(n.L, k);
    if (S(n.L) == k) return n.label;
    return kth(n.R, k - S(n.L) - 1);
}

void addAll(int r, int &to){    // add all nodes in 'r' to 'to'
    if (r == -1) return;
    addAll(node[r].L, to);
    addAll(node[r].R, to);
    add(to, node[r].label);
}

void removeAll(int r){      // free all nodes in 'r'
    if (r == -1) return;
    removeAll(node[r].L);
    removeAll(node[r].R);
    fnode.push_back(r);     // r is free, claim back the index
}

vector<int> con[MAXN], qk[MAXN], qi[MAXN];
int T,N,Q,L,a,b,k,x, ans[MAXN], label[MAXN];

int dfs(int x){
    int root = -1; // new tree
    REP(i,con[x].size()) if (x || con[x][i]){ // avoid 0's parent
        int r = dfs(con[x][i]);
        if (S(root) < S(r)) swap(root,r);   // pick the largest tree as the root
        addAll(r, root);    // transfer r's nodes to root's
        removeAll(r);       // delete unused tree
    }
    add(root,label[x]);     // post order insert
    REP(i,qk[x].size())     // answer all queries for node x (this node)
        ans[qi[x][i]] = kth(root, qk[x][i] - 1);
    return root;
}

int main(){
    REP(i,MAXN) fnode.push_back(i); // setup free indices
    scanf("%d",&T);
    REP(t,T){
        scanf("%d %d",&N,&Q);
        REP(i,N) con[i].clear(), qk[i].clear(), qi[i].clear(), scanf("%d",&label[i]);
        REP(a,N) scanf("%d",&b), con[b].push_back(a);
        REP(i,Q) scanf("%d %d",&k,&x), qk[x].push_back(k), qi[x].push_back(i);
        int root = dfs(0);  // traverse tree, and answer queries
        removeAll(root);    // delete tree
        printf("Case #%d:\n",t+1);
        REP(i,Q) printf("%d\n",ans[i]);
    }
}

7 5
17 13 15 9 16 16 3 18 11 5 11 6 18 1 6 14 18 6
18 14 9 8 2 10 10 16 6 11 6 16 10 20 8 5 15 6 2
17 7 6 14 9 9 7 5 13 5 17 17 9 19 9 5 2 16
19 7 6 19 13 18 12 16 2 12 13 7 2 20 17 11 8 5 6 12
20 10 13 13 9 9 10 14 15 16 9 4 9 5 5 13 8 20 13 7 7
18 16 13 13 11 10 18 12 17 18 6 17 4 3 19 9 16 4 10
20 11 2 4 19 13 8 16 17 11 18 15 5 3 9 11 19 3 19 6 18
10 18 12 17 18 6 17 4 3 19
13 13 11 10 18 12 17 18 6 17
11 12 17 7 8 5 6 8 3 16
15 16 9 4 9 5 5 13 8 20
16 6 11 6 16 10 20 8 5 15

6 5
6 2
not found
5 8
2 7

Pembahasan Soal G - Finding The Right Song

Soal ini saya buat karena ter-inspirasi oleh Shazam. Shazam adalah suatu applikasi iPhone yang dapat mengenali lagu yang sedang dimainkan dengan cara merekam 10 detik di bagian manapun dari lagu yang sedang dimainkan. Rekaman 10 detik tersebut kemudian dikirim ke server Shazam dan servernya akan memberitahu nama lagu tersebut. Shazam memiliki 20 ribu lagu dan hanya membutuhkan beberapa milisecond untuk pencariannya.

Soal ini adalah versi simplenya dari masalah yang dihadapi Shazam dan tentunya dapat diselesaikan dengan cara yang sama dengan Shazam, yaitu menggunakan hash table. Hash table ini akan diisi dengan potongan-potongan 10 detik dari semua bagian dari semua lagu yang ada. Sehingga, kalau kita memiliki query yang berisi 10 detik potongan lagu, kita dapat mencari (lookup) nama lagu tersebut dan posisi dimulainya potongan tersebut dari dalam hash table dalam O(1) expected.

Linear probing mungkin adalah cara termudah yang dapat digunakan untuk mengatasi hash collisions dimana ada dua melodi mempunyai hash value yang sama. Saya sengaja membuat soal ini untuk hanya bisa solve menggunakan hash table buatan sendiri atau dengan meng-override HashMap (bagi pengguna Java). Mereka yang menggunakan STL-map akan mendapatkan TLE karena STL-map di-implementasi menggunakan Red-Black tree yang membutuhkan O(log N) operasi untuk mengakses elemen di dalamnya. Berikut adalah contoh implementasinya.

#include <stdio.h>
#include <assert.h>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

#define HSIZE 3000001
#define IS_EMPTY(key) (e[key].song == -1)
#define QLEN 10

struct Entry { short song, pos; } e[HSIZE];
int songs[2001][1001], query[10], N,Q,S;

bool equal(int *a, int *b){
    REP(i,QLEN) if (a[i]!=b[i]) return false;
    return true;
}

int lookup(int *melody){
    unsigned int H = 0;                     // the hash of the melody
    REP(i,QLEN) H += (H*13) ^ melody[i];    // simple hash function
    REP(i,HSIZE){
        int key = (H + i) % HSIZE;          // http://en.wikipedia.org/wiki/Linear_probing
        if (IS_EMPTY(key)) return -key;
        int *this_melody = songs[e[key].song] + e[key].pos;
        if (equal(melody, this_melody)) return key;
    }
    assert(false);                          // hash table is full!
}

int main(){
    REP(i,HSIZE) e[i].song = -1;            // set hash table to empty
    scanf("%d %d",&N,&Q);
    REP(i,N){
        scanf("%d",&S);
        REP(j,S) scanf("%d",&songs[i][j]);
        REP(j,S-QLEN+1){
            int key = -lookup(songs[i]+j);  // expected O(1)
            assert(key >= 0);               // should have no duplicate!
            e[key] = (Entry){i,j};          // insert into hash table
        }
    }
    REP(i,Q){
        REP(j,QLEN) scanf("%d",&query[j]);
        int key = lookup(query);            // expected O(1)
        if (key < 0) puts("not found");
        else printf("%d %d\n", e[key].song+1, e[key].pos+1);
    }
}

Problem H - Disconnected Graph

Time Limit: 10s

Given an undirected connected simple graph of N nodes and E edges. There are up to Q nodes selected from N nodes that are special nodes. Suppose that R selected edges are destroyed, your task is to calculate how many pairs of node A-B where A and B belong to special nodes, are disconnected (there is no path from A to B or vice versa after R edges are destroyed).

Input

The first line of input contains an integer T (1 ≤ T ≤ 50) the number of cases. Each case begins with four integers N, E, Q and R (1 ≤ Q ≤ N ≤ 50,000; 0 ≤ R ≤ E ≤ 200,000) denoting the number of nodes, edges, special nodes, and destroyed edges respectively. The nodes are numbered from 1 to N. The next E line each contains two integers A_i and B_i (1 ≤ A_i, B_i ≤ N) representing an edge connecting node A and node B. The next line contains Q integers P_i (1 ≤ P_i ≤ N) denoting the selected special nodes. The next line contains R integers T_i (1 ≤ T_i ≤ E) denoting the edges that are destroyed (the edges are numbered from 1 to E based on input order).

Output

For each case, output in a single line a number denoting the number of disconnected pair of special nodes.

Sample Input Output for Sample Input 2 4 4 4 3 1 2 1 4 2 4 3 4 1 2 3 4 1 2 3 2 1 1 1 1 2 2 1 5 0

Explanation for the 1^st sample input

There 5 pair of special nodes that are disconnected: 1-2, 1-3, 1-4, 2-3 and 2-4.

Explanation for the 2^nd sample input

There is only one special node, so we can't have any pair of them.

---

Pembahasan Soal H - Disconnected Graph

Soal ini bisa disederhanakan dengan membuang semua edge yang dihancurkan. Dari graph yang ada, kita cari ada berapa banyak node yang spesial dalam suatu komponen yang terhubung. Suatu komponen yang terhubung bisa dicari dengan DFS atau disjoint set. Setelah kita mengetahui banyaknya node yang special di dalam komponen-komponen terhubung yang ada, untuk menghitung banyaknya pair antara 2 special node yang berada di komponen berbeda dapat dilakukan dengan mengalikan banyaknya special node yang ada di dalam komponen dengan banyaknya special node yang ada di luar komponen.

Berikut adalah contoh implementasi menggunakan disjoint set.

#include <stdio.h>

#define REP(i,n) for (int i=0,_n=(n); i<_n; i++)

int T,N,E,Q,R,a,b,P[50010],pset[50010],ea[200010],eb[200010],D[200010];
int findSet(int i){ return (pset[i]==i)? i : (pset[i] = findSet(pset[i])); }
void merge(int i, int j){ pset[findSet(i)] = findSet(j); }
int sameSet(int i, int j){ return findSet(i)==findSet(j); }

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d %d %d",&N,&E,&Q,&R);
        REP(i,N+1) pset[i] = i, P[i] = 0;
        REP(i,E) scanf("%d %d",&ea[i],&eb[i]), D[i] = 0;
        REP(i,Q) scanf("%d",&a), P[a] = 1;
        REP(i,R) scanf("%d",&a), D[a-1] = 1;
        REP(i,E) if (!D[i] && !sameSet(ea[i],eb[i])){
            a = P[findSet(ea[i])];   // a = banyaknya special node di komponen ea[i]
            b = P[findSet(eb[i])];   // b = banyaknya special node di komponen eb[i]
            merge(ea[i],eb[i]);      // gabung komponen ea[i] dengan eb[i]
            P[findSet(ea[i])] = a+b; // banyaknya special node gabungan adalah a+b
        }
        long long res = 0;
        REP(i,N){
            a = findSet(i+1);        // a = komponen dari node i
            b = P[a];                // b = banyaknya special node di komponen a
            res += (Q-b)*b;          // (banyaknya special node di luar komponen a) * b
            P[a] = 0;                // komponen a telah diprocess
        }
        printf("%lld\n",res/2);      // double counting
    }
}

Problem I - Maximum Sum in Matrix

Time Limit: 3s

Given a matrix A of size N x M, write a program to find p₁, p₂, ..., p_n to maximize A[1][p₁] + A[2][p₂] + ... + A[n][p_n]. You are only allowed to change p_i no more than K times (changes occur when p_i is not equal to p_i-1). You may choose p₁ anywhere from 1 to M and it will not be counted as a change.

For example, given a matrix of 7 x 4 as shown below and K = 3.

The maximum sum that you can get is 8 + 10 + 7 + 3 + 9 + 20 + 15 = 72. But if you are only allowed to make changes at most one time (K = 1), then the maximum sum that you can get is 59.

Input

The first line of input contains an integer T (1 ≤ T ≤ 100) the number of cases. Each case begins with three integers N, M and K (1 ≤ N ≤ 100; 1 ≤ M ≤ 10; 0 ≤ K < N). The next N lines each contains M integers representing the given matrix. Each integer in the matrix is between 1 and 1,000 inclusive.

Output

For each case, output in a single line the maximum sum that you can get from the matrix.

Sample Input Output for Sample Input 2 7 4 3 3 8 5 2 12 1 4 10 1 5 6 7 2 3 4 3 1 7 2 9 4 20 3 1 5 3 15 8 7 4 1 3 8 5 2 12 1 4 10 1 5 6 7 2 3 4 3 1 7 2 9 4 20 3 1 5 3 15 8 72 59

---

Pembahasan Soal I - Maximum Sum in Matrix

States dari dynamic programming nya adalah dp[n][m][k] seperti yang dijelaskan di blog Suhendry dan Eko. Dalam implementasinya, kita hanya membutuhkan value dari dua state terakhir: dp[i] dan dp[i-1]. Sehingga kita dapat menghemat memory. Banyak yang bilang ini adalah "dp terbang" atau "dp on the fly". Berikut adalah contoh implementasinya.

#include <stdio.h>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)

int T,N,M,K,X,dp[2][102][102];

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d %d %d",&N,&M,&K);
        REP(i,N) REP(j,M){
            int (*c)[102] = dp[i%2];
            int (*p)[102] = dp[1-(i%2)];
            scanf("%d",&X);
            if (i==0){
                REP(k,K+1) c[j][k] = 0;
                c[j][0] = X;
            } else {
                REP(k,K+1) c[j][k] = p[j][k] + X;
                REP(k,K+1) REP(m,M)
                    c[j][k+(j==m?0:1)] >?= p[m][k] + X;
            }
        }
        int res = 0;
        REP(i,M) REP(j,K+1) res >?= dp[1-N%2][i][j];
        printf("%d\n",res);
    }
}