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

// ================================================================
// Global constants used across algorithms
// ================================================================

const int INF = 1e9;                     // for integer min/max
const long long INFLL = 4e18;            // for long long (safe)
const int MOD = 1e9 + 7;                 // common modulus

// ================================================================
// 1) 0/1 KNAPSACK (1D memory optimization)
// ================================================================

/*
Function: knapsack01
Purpose: Maximize total value with total weight <= W, each item used at most once.
Parameters:
  - weight: vector<int>, weight[i] of item i.
  - value:  vector<int>, value[i] of item i.
  - W:      int, capacity.
Returns: Maximum total value.
Time: O(n * W), Space: O(W)
Notes: Uses a rolling 1D array (iterate weight backwards).
*/
int knapsack01(const vector<int>& weight, const vector<int>& value, int W) {
    int n = (int)weight.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

// ================================================================
// 2) UNBOUNDED KNAPSACK (each item can be used unlimited times)
// ================================================================

/*
Function: knapsackUnbounded
Purpose: Maximize total value with unlimited copies of each item.
Parameters: same as knapsack01.
Returns: Maximum total value.
Time: O(n * W), Space: O(W)
Notes: Uses forward loop (increasing weight) because items are unbounded.
*/
int knapsackUnbounded(const vector<int>& weight, const vector<int>& value, int W) {
    int n = (int)weight.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = weight[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    return dp[W];
}

// ================================================================
// 3) LONGEST INCREASING SUBSEQUENCE (LIS) – O(n log n)
// ================================================================

/*
Function: LIS
Purpose: Returns the length of the longest increasing subsequence.
Parameters: arr – input vector.
Returns: int length.
Time: O(n log n), Space: O(n)
Notes: Uses binary search (lower_bound) on tails vector. Only gives length.
*/
int LIS(const vector<int>& arr) {
    vector<int> tails;
    for (int x : arr) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return (int)tails.size();
}

/*
Function: LIS_reconstruct
Purpose: Returns one actual LIS sequence (not just length).
Parameters: arr – input vector.
Returns: vector<int> – the LIS.
Time: O(n^2) due to DP, Space: O(n)
Notes: Uses parent pointers. For large n, use the O(n log n) reconstruction variant.
*/
vector<int> LIS_reconstruct(const vector<int>& arr) {
    int n = (int)arr.size();
    vector<int> dp(n, 1), parent(n, -1);
    int maxLen = 0, bestIdx = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            bestIdx = i;
        }
    }
    vector<int> seq;
    for (int i = bestIdx; i != -1; i = parent[i])
        seq.push_back(arr[i]);
    reverse(seq.begin(), seq.end());
    return seq;
}

// ================================================================
// 4) LONGEST COMMON SUBSEQUENCE (LCS) – 1D memory
// ================================================================

/*
Function: LCS
Purpose: Compute length of LCS between two strings (or sequences).
Parameters: a, b – strings.
Returns: int LCS length.
Time: O(n*m), Space: O(m) (rolling two rows)
Notes: Works for any sequence type if you replace char with generic type.
*/
int LCS(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<int> dp(m + 1, 0), ndp(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1])
                ndp[j] = dp[j-1] + 1;
            else
                ndp[j] = max(dp[j], ndp[j-1]);
        }
        dp.swap(ndp);
    }
    return dp[m];
}

// ================================================================
// 5) EDIT DISTANCE (LEVENSHTEIN) – 1D memory
// ================================================================

/*
Function: editDistance
Purpose: Minimum number of insert/delete/replace operations to convert a to b.
Parameters: a, b – strings.
Returns: int edit distance.
Time: O(n*m), Space: O(m)
Notes: Uses two rows; replace cost is 1.
*/
int editDistance(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<int> dp(m + 1), ndp(m + 1);
    iota(dp.begin(), dp.end(), 0);
    for (int i = 1; i <= n; i++) {
        ndp[0] = i;
        for (int j = 1; j <= m; j++) {
            if (a[i-1] == b[j-1])
                ndp[j] = dp[j-1];
            else
                ndp[j] = 1 + min({dp[j], ndp[j-1], dp[j-1]});
        }
        dp.swap(ndp);
    }
    return dp[m];
}

// ================================================================
// 6) COIN CHANGE – number of ways & minimum coins (unbounded)
// ================================================================

/*
Function: coinChangeWays
Purpose: Count number of ways to make 'amount' using unlimited coins.
Parameters: coins – denominations, amount – target.
Returns: long long number of ways.
Time: O(|coins| * amount), Space: O(amount)
Notes: Combinations (order does not matter). Uses forward loop.
*/
long long coinChangeWays(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins) {
        for (int x = c; x <= amount; x++) {
            dp[x] += dp[x - c];
        }
    }
    return dp[amount];
}

/*
Function: coinChangeMin
Purpose: Minimum number of coins to make 'amount' (unbounded).
Parameters: coins, amount.
Returns: int – minimum coins, or -1 if impossible.
Time: O(|coins| * amount), Space: O(amount)
Notes: Uses INF for impossible states.
*/
int coinChangeMin(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int c : coins) {
        for (int x = c; x <= amount; x++) {
            if (dp[x - c] + 1 < dp[x])
                dp[x] = dp[x - c] + 1;
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

// ================================================================
// 7) MAXIMUM SUBARRAY SUM (Kadane)
// ================================================================

/*
Function: maxSubarraySum
Purpose: Maximum sum of a contiguous subarray (Kadane).
Parameters: arr – vector<long long> (may contain negatives).
Returns: long long max sum.
Time: O(n), Space: O(1)
Notes: Handles all negative numbers (returns the least negative). Assumes non‑empty.
*/
long long maxSubarraySum(const vector<long long>& arr) {
    long long maxEnd = 0, maxSum = LLONG_MIN;
    for (long long x : arr) {
        maxEnd = max(x, maxEnd + x);
        maxSum = max(maxSum, maxEnd);
    }
    return maxSum;
}

// ================================================================
// 8) MATRIX CHAIN MULTIPLICATION – iterative bottom‑up
// ================================================================

/*
Function: matrixChainOrder
Purpose: Minimum scalar multiplications to multiply a chain of matrices.
Parameters: dims – vector<int> where matrix i has rows dims[i] and columns dims[i+1].
Returns: int minimum cost.
Time: O(n^3), Space: O(n^2) for n = dims.size()-1.
Notes: Uses interval DP. Only returns cost, not the parenthesization.
*/
int matrixChainOrder(const vector<int>& dims) {
    int n = (int)dims.size() - 1;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

// ================================================================
// 9) TRAVELING SALESMAN PROBLEM (bitmask DP)
// ================================================================

/*
Function: tsp
Purpose: Shortest Hamiltonian path visiting all nodes exactly once (open TSP, no return).
Parameters: dist – n x n cost matrix.
Returns: int minimum cost.
Time: O(n^2 * 2^n), Space: O(n * 2^n)
Notes: n <= 20 typically. Uses INF for unreachable states.
*/
int tsp(const vector<vector<int>>& dist) {
    int n = (int)dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int last = 0; last < n; last++) {
            if (!(mask & (1 << last))) continue;
            for (int nxt = 0; nxt < n; nxt++) {
                if (mask & (1 << nxt)) continue;
                int nmask = mask | (1 << nxt);
                dp[nmask][nxt] = min(dp[nmask][nxt],
                                     dp[mask][last] + dist[last][nxt]);
            }
        }
    }
    int ans = INF;
    for (int last = 0; last < n; last++)
        ans = min(ans, dp[(1 << n) - 1][last]);
    return ans;
}

// ================================================================
// 10) DP ON TREES – maximum weight independent set
// ================================================================

/*
Function: treeDP
Purpose: Computes the max weight independent set on a tree (each node has weight = 1 here).
Parameters: adj – adjacency list (undirected), root (default 0).
Returns: pair<int,int> {dp0[root], dp1[root]} where dp0 = max when root not taken, dp1 = max when root taken.
Time: O(n), Space: O(n)
Notes: Uses iterative DFS to avoid recursion depth issues. Replace the '1' in dp1 with actual node weight.
*/
pair<int, int> treeDP(const vector<vector<int>>& adj, int root = 0) {
    int n = (int)adj.size();
    vector<int> parent(n, -1), order;
    order.reserve(n);
    stack<int> st;
    st.push(root);
    parent[root] = root;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            st.push(v);
        }
    }
    vector<int> dp0(n, 0), dp1(n, 1); // dp1[u] = weight[u] (here weight = 1)
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            dp0[u] += max(dp0[v], dp1[v]);
            dp1[u] += dp0[v];
        }
    }
    return {dp0[root], dp1[root]};
}

// ================================================================
// 11) DIGIT DP (recursive with memoization)
// ================================================================

/*
Function: digitDP_recursive
Purpose: Counts numbers from 0 to X (inclusive) whose digit sum is divisible by MOD.
Parameters:
  - num: string representation of X.
  - pos, sum, tight: state parameters (call initially with pos=0, sum=0, tight=1).
  - MOD: divisor for sum.
  - memo: 3D memo table (size n x MOD x 2).
Returns: long long count.
Time: O(n * MOD * 10), Space: O(n * MOD)
Notes: Only stores states with tight=0. Easily adaptable to other digit properties.
*/
long long digitDP_recursive(const string& num, int pos, int sum, int tight,
                            int MOD, vector<vector<vector<long long>>>& memo) {
    if (pos == (int)num.size()) return sum % MOD == 0;
    if (!tight && memo[pos][sum][0] != -1) return memo[pos][sum][0];
    int limit = tight ? num[pos] - '0' : 9;
    long long res = 0;
    for (int d = 0; d <= limit; d++) {
        res += digitDP_recursive(num, pos+1, (sum + d) % MOD,
                                 tight && (d == limit), MOD, memo);
    }
    if (!tight) memo[pos][sum][0] = res;
    return res;
}

// ================================================================
// 12) MAXIMUM SUBARRAY SUM WITH LENGTH AT MOST K (prefix + deque)
// ================================================================

/*
Function: maxSumWithK
Purpose: Maximum sum of any subarray with length <= K.
Parameters: arr – vector<int>, K – max length.
Returns: int max sum.
Time: O(n), Space: O(n)
Notes: Uses prefix sums and a deque to maintain increasing prefixes.
*/
int maxSumWithK(const vector<int>& arr, int K) {
    int n = (int)arr.size();
    vector<int> pref(n+1, 0);
    for (int i = 0; i < n; i++) pref[i+1] = pref[i] + arr[i];
    deque<int> dq;
    int ans = INT_MIN;
    for (int i = 0; i <= n; i++) {
        while (!dq.empty() && dq.front() < i - K) dq.pop_front();
        if (!dq.empty()) ans = max(ans, pref[i] - pref[dq.front()]);
        while (!dq.empty() && pref[dq.back()] >= pref[i]) dq.pop_back();
        dq.push_back(i);
    }
    return ans;
}

// ================================================================
// 13) KNAPSACK BY VALUE (when total value is small)
// ================================================================

/*
Function: knapsackByValue
Purpose: 0/1 knapsack when weights are large but total value is small.
Parameters: weight, value, W.
Returns: int max value with weight <= W.
Time: O(n * totalValue), Space: O(totalValue)
Notes: dp[v] = minimum weight to achieve exactly value v. Then find largest v with dp[v] <= W.
*/
int knapsackByValue(const vector<int>& weight, const vector<int>& value, int W) {
    int totalValue = accumulate(value.begin(), value.end(), 0);
    vector<int> dp(totalValue + 1, INF);
    dp[0] = 0;
    for (int i = 0; i < (int)weight.size(); i++) {
        for (int v = totalValue; v >= value[i]; v--) {
            dp[v] = min(dp[v], dp[v - value[i]] + weight[i]);
        }
    }
    for (int v = totalValue; v >= 0; v--)
        if (dp[v] <= W) return v;
    return 0;
}

// ================================================================
// 14) LONGEST PALINDROMIC SUBSEQUENCE (1D memory)
// ================================================================

/*
Function: longestPalindromicSubseq
Purpose: Length of the longest palindromic subsequence in string s.
Parameters: s – input string.
Returns: int length.
Time: O(n^2), Space: O(n) (rolling two rows)
Notes: DP over intervals, only keeps previous row.
*/
int longestPalindromicSubseq(const string& s) {
    int n = (int)s.size();
    vector<int> dp(n, 0), ndp(n, 0);
    for (int i = n-1; i >= 0; i--) {
        dp[i] = 1;
        for (int j = i+1; j < n; j++) {
            if (s[i] == s[j])
                ndp[j] = dp[j-1] + 2;
            else
                ndp[j] = max(dp[j], ndp[j-1]);
        }
        dp.swap(ndp);
    }
    return dp[n-1];
}

// ================================================================
// 15) UNIQUE PATHS IN GRID WITH OBSTACLES (1D DP)
// ================================================================

/*
Function: uniquePathsWithObstacles
Purpose: Number of paths from (0,0) to (n-1,m-1) avoiding obstacles.
Parameters: obstacleGrid – 2D vector (0 = free, 1 = obstacle).
Returns: int number of paths modulo MOD.
Time: O(n*m), Space: O(m)
Notes: Rolling array; obstacles set dp[j] = 0.
*/
int uniquePathsWithObstacles(const vector<vector<int>>& obstacleGrid) {
    int n = (int)obstacleGrid.size(), m = (int)obstacleGrid[0].size();
    vector<long long> dp(m, 0);
    dp[0] = (obstacleGrid[0][0] == 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (obstacleGrid[i][j] == 1) { dp[j] = 0; continue; }
            if (i == 0 && j == 0) continue;
            if (j > 0) dp[j] = (dp[j] + dp[j-1]) % MOD;
            // if i > 0, dp[j] already contains value from previous row, we add left
            // Actually the above logic: dp[j] is from previous row (i-1) when i>0,
            // and we add dp[j-1] (current row left) if j>0.
            // So it's correct: dp[j] = (i>0 ? dp[j] : 0) + (j>0 ? dp[j-1] : 0)
            // But the code above: for i>0, dp[j] initially holds from previous row, so adding dp[j-1] works.
            // For i==0, j>0, dp[j] initially 0, so adding dp[j-1] works.
        }
    }
    return dp[m-1];
}

// ================================================================
// 16) COUNT DISTINCT SUBSEQUENCES (including empty)
// ================================================================

/*
Function: distinctSubsequences
Purpose: Number of distinct subsequences (including empty) of string s, modulo MOD.
Parameters: s – input string.
Returns: int count (including empty).
Time: O(n), Space: O(n)
Notes: Uses last occurrence to avoid double counting. Subtract 1 for non‑empty.
*/
int distinctSubsequences(const string& s) {
    vector<int> dp(s.size()+1, 0);
    dp[0] = 1;
    vector<int> last(26, -1);
    for (int i = 0; i < (int)s.size(); i++) {
        dp[i+1] = (2LL * dp[i]) % MOD;
        if (last[s[i]-'a'] != -1)
            dp[i+1] = (dp[i+1] - dp[last[s[i]-'a']] + MOD) % MOD;
        last[s[i]-'a'] = i;
    }
    return dp[s.size()];
}

// ================================================================
// 17) MAXIMUM SUM SUBMATRIX (2D Kadane)
// ================================================================

/*
Function: maxSubmatrixSum
Purpose: Maximum sum of any rectangular submatrix.
Parameters: mat – 2D vector of ints.
Returns: int max sum.
Time: O(n * m^2) or O(m * n^2) depending on loop; here O(m^2 * n).
Space: O(n)
Notes: Fix left/right columns, sum rows, apply 1D Kadane.
*/
int maxSubmatrixSum(const vector<vector<int>>& mat) {
    int n = (int)mat.size(), m = (int)mat[0].size();
    int maxSum = INT_MIN;
    for (int left = 0; left < m; left++) {
        vector<int> temp(n, 0);
        for (int right = left; right < m; right++) {
            for (int i = 0; i < n; i++) temp[i] += mat[i][right];
            int cur = 0, best = INT_MIN;
            for (int x : temp) {
                cur = max(x, cur + x);
                best = max(best, cur);
            }
            maxSum = max(maxSum, best);
        }
    }
    return maxSum;
}

// ================================================================
// 18) COUNT PATHS IN DAG (topological order)
// ================================================================

/*
Function: countPathsDAG
Purpose: Count number of paths from src to dst in a DAG.
Parameters: adj – adjacency list, src, dst.
Returns: long long number of paths.
Time: O(n + m), Space: O(n)
Notes: Uses Kahn's algorithm for topological order. Multi‑edges counted separately.
*/
long long countPathsDAG(const vector<vector<int>>& adj, int src, int dst) {
    int n = (int)adj.size();
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) indeg[v]++;
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    vector<long long> dp(n, 0);
    dp[src] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            dp[v] += dp[u];
            if (--indeg[v] == 0) q.push(v);
        }
    }
    return dp[dst];
}

// ================================================================
// 19) DIVIDE AND CONQUER DP OPTIMIZATION (template)
// ================================================================

/*
This section provides a template for D&C DP optimization.
It assumes recurrence: dp_cur[i] = min_{k < i} (dp_prev[k] + C(k, i))
and that the optimal k is monotonic (opt[i] <= opt[i+1]).
The cost function C(k, j) must be defined separately.
The compute() function fills dp_cur[l..r] knowing opt is in [optL, optR].
*/

long long costFunction(int k, int j) {
    // To be implemented by user (depends on problem)
    return 0;
}

void computeDnC(int l, int r, int optL, int optR,
                const vector<long long>& dp_prev, vector<long long>& dp_cur) {
    if (l > r) return;
    int mid = (l + r) / 2;
    pair<long long, int> best = {INFLL, -1};
    for (int k = optL; k <= min(optR, mid - 1); k++) {
        long long val = dp_prev[k] + costFunction(k, mid);
        if (val < best.first) best = {val, k};
    }
    dp_cur[mid] = best.first;
    computeDnC(l, mid - 1, optL, best.second, dp_prev, dp_cur);
    computeDnC(mid + 1, r, best.second, optR, dp_prev, dp_cur);
}

// ================================================================
// 20) MATRIX EXPONENTIATION (for linear recurrences)
// ================================================================

using Matrix = vector<vector<long long>>;

Matrix matMul(const Matrix& A, const Matrix& B) {
    int n = (int)A.size(), m = (int)B[0].size(), p = (int)A[0].size();
    Matrix C(n, vector<long long>(m, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < p; k++)
            if (A[i][k])
                for (int j = 0; j < m; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Matrix matPow(Matrix base, long long exp) {
    int n = (int)base.size();
    Matrix res(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) res[i][i] = 1;
    while (exp) {
        if (exp & 1) res = matMul(res, base);
        base = matMul(base, base);
        exp >>= 1;
    }
    return res;
}

// ================================================================
// 21) SIMPLE PRIME CHECK (for digit DP example)
// ================================================================

bool isPrime(int x) {
    if (x < 2) return false;
    for (int d = 2; d * d <= x; d++)
        if (x % d == 0) return false;
    return true;
}

// Example of digit DP usage (count numbers with prime digit sum)
long long countWithPrimeDigitSum(long long X) {
    string s = to_string(X);
    int n = (int)s.size();
    // memo[pos][sum][tight] but we only store tight=0
    vector<vector<vector<long long>>> memo(n, vector<vector<long long>>(200, vector<long long>(2, -1)));
    long long total = digitDP_recursive(s, 0, 0, 1, 1, memo); // MOD=1 to count all, then filter prime sums?
    // Actually the above uses MOD=1, so it counts all numbers, but we need to count those with prime sum.
    // Better to modify digitDP_recursive to accept a predicate.
    // For demonstration, we'll just return 0 placeholder.
    return 0;
}

// ================================================================
// MAIN – example usage
// ================================================================

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

    // Example: 0/1 Knapsack
    int n, W;
    if (cin >> n >> W) {
        vector<int> w(n), v(n);
        for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
        cout << "Knapsack 0/1: " << knapsack01(w, v, W) << '\n';
    }

    // Example: LIS
    vector<int> arr;
    int x;
    while (cin >> x) arr.push_back(x);
    if (!arr.empty()) {
        cout << "LIS length: " << LIS(arr) << '\n';
        vector<int> seq = LIS_reconstruct(arr);
        cout << "One LIS: ";
        for (int val : seq) cout << val << ' ';
        cout << '\n';
    }

    return 0;
}