#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
vector<int>solve(vector<int>& cost, vector<string>& aa) {
    int n = cost.size();
    vector<int> result(n, -1);
    vector<int> costA, costB, costBoth;
        for (int i = 0; i < n; ++i) {
        if (aa[i] == "10") {
            costA.push_back(cost[i]);
        } else if (aa[i] == "01") {
            costB.push_back(cost[i]);
        } else if (aa[i] == "11") {
            costBoth.push_back(cost[i]);
        }
    }
    sort(costA.begin(), costA.end());
    sort(costB.begin(), costB.end());
    sort(costBoth.begin(), costBoth.end());
    
    vector<int> prefixA(costA.size() + 1, 0);
    vector<int> prefixB(costB.size() + 1, 0);
    vector<int> prefixBoth(costBoth.size() + 1, 0);
    
    for (int i = 0; i < costA.size(); ++i) prefixA[i + 1] = prefixA[i] + costA[i];
    for (int i = 0; i < costB.size(); ++i) prefixB[i + 1] = prefixB[i] + costB[i];
    for (int i = 0; i < costBoth.size(); ++i) prefixBoth[i + 1] = prefixBoth[i] + costBoth[i];
    
    for (int k = 1; k <= n; ++k) {
        int minCost = INT_MAX;
                for (int i = 0; i <= min(k, (int)costBoth.size()); ++i) {
            if (k - i <= (int)costA.size() && k - i <= (int)costB.size()) {
                int currentCost = prefixBoth[i] + prefixA[k - i] + prefixB[k - i];
                minCost = min(minCost, currentCost);
            }
        }
        
        if (minCost != INT_MAX) {
            result[k - 1] = minCost;
        }
    }
    
    return result;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int bfs(int start, vector<vector<int>>& adj, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    int size = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        size++;
        
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    
    return size;
}
int solve(int K) {
    vector<int> primes;
    int num = 2; 
    while (primes.size() < K) {
        bool is_prime = true;
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            primes.push_back(num);
        }
        num++;
    }
    
    return primes[K-1];
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int U, V;
        cin >> U >> V;
        adj[U].push_back(V);
        adj[V].push_back(U);
    }
    vector<bool> visited(N + 1, false);
    int max_landmarks = 0;
    
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            int component_size = bfs(i, adj, visited);
            max_landmarks = max(max_landmarks, component_size);
        }
    }
    int ticket_price = solve(max_landmarks);
    cout << max_landmarks << " " << ticket_price << endl;
    
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <functional>
#include <algorithm>
using namespace std;
struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        if (a.second == b.second) return a.first > b.first;
        return a.second < b.second; 
    }
};

int main() {
    int N;
    cin >> N;
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    unordered_map<int, int> elementPriority;
    unordered_map<int, bool> removedElements;
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        pq.push({x, y});
        elementPriority[x] = y; 
        removedElements[x] = false;
    }

    int K;
    cin >> K;
    for (int i = 0; i < K && !pq.empty(); ++i) {
        int removedElement = pq.top().first;
        pq.pop();
        removedElements[removedElement] = true; 
    }

    vector<pair<int, int>> remainingElements;
    for (const auto& entry : elementPriority) {
        if (!removedElements[entry.first]) {
            remainingElements.push_back({entry.first, entry.second});
        }
    }

    sort(remainingElements.begin(), remainingElements.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.second == b.second) return a.first < b.first; 
        return a.second > b.second; 
    });

    for (const auto& el : remainingElements) {
        cout << el.first << endl;
    }

    return 0;
}

#include <iostream>
#include <string>
using namespace std;
string solve(const string& str1, const string& str2) {
    string result;
        for (size_t i = 0; i < str1.size(); ++i) {
        if (str1[i] != str2[i]) {
            result += str2[i];
        }
    }
    
    return result;
}

int main() {
    string str1, str2;
        cin >> str1 >> str2;
    
    cout << solve(str1, str2) << endl;
    
    return 0;
}

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

vector<int> solve(int N, vector<ll>& A, vector<pair<int, int>>& edges, int Q, vector<pair<ll, int>>& queries) {
    vector<vector<int>> adj(N + 1);
    for (auto& edge : edges) {
        int u = edge.first, v = edge.second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    auto toBinary = [](ll value) {
        string binary = bitset<62>(value).to_string();
        return binary;
    };

    vector<string> binaryValues(N + 1);
    for (int i = 1; i <= N; ++i) {
        binaryValues[i] = toBinary(A[i-1]);
    }

    vector<vector<int>> ancestors(N + 1);
    vector<int> parent(N + 1, -1);

    function<void(int, int)> dfs = [&](int node, int par) {
        parent[node] = par;
        if (par != -1) {
            ancestors[node] = ancestors[par];
            ancestors[node].push_back(par);
        }
        for (int neighbor : adj[node]) {
            if (neighbor == par) continue;
            dfs(neighbor, node);
        }
    };

    dfs(1, -1);

    auto longestCommonPrefix = [](const string& a, const string& b) {
        int len = 0;
        while (len < a.size() && a[len] == b[len]) {
            ++len;
        }
        return len;
    };

    vector<int> ans;
    for (auto& query : queries) {
        ll V = query.first;
        int X = query.second;
        string V_binary = toBinary(V);

        int maxLength = 0;
        for (int ancestor : ancestors[X]) {
            int lcp = longestCommonPrefix(V_binary, binaryValues[ancestor]);
            maxLength = max(maxLength, lcp);
        }
        int lcp = longestCommonPrefix(V_binary, binaryValues[X]);
        maxLength = max(maxLength, lcp);

        ans.push_back(maxLength);
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<ll> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }
        vector<pair<int, int>> edges(N - 1);
        for (int i = 0; i < N - 1; ++i) {
            int u, v;
            cin >> u >> v;
            edges[i] = {u, v};
        }
        int Q;
        cin >> Q;
        vector<pair<ll, int>> queries(Q);
        for (int i = 0; i < Q; ++i) {
            cin >> queries[i].first >> queries[i].second;
        }

        vector<int> results = solve(N, A, edges, Q, queries);
        for (int result : results) {
            cout << result << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll solve(vector<ll>&a,ll k)
{
  ll n=a.size();
  ll s=0,st=0,en=0,maxsofar=0,maxend=0;
  for(ll i=0;i<n;i++)
  {
    maxend+=a[i];
    if(maxsofar<maxend)
    {
      maxsofar=maxend;
      st=s;
      en=i;
    }
    if(maxend<0)
    {
      maxend=0;
      s=i+1;
    }
  }
  return maxsofar+k*(en-st);
}
signed main() 
{
    ll n,k; cin>>n>>k;
  vector<ll>a(n);
  for(ll i=0;i<n;i++) cin>>a[i];
  cout<<solve(a,k);
    return 0;            
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
     int T;
    cin >> T;

    while (T--) {
    ll n, m, k;
    cin >> n >> m >> k;
    vector<vector<long long>> v(n, vector<long long>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
    }
    vector<pair<long long, long long>> a;
    for (int i = 0; i < n; i++) {
        long long x = 0;
        long long count = 0;
        for (int j = 0; j < m; j++) {
            if (v[i][j]) {
                x |= (1LL << j);
            } else {
                count++;
            }
        }
        a.push_back({x, count});
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long curr = 0;
        for (int j = 0; j < n; j++) {
            if (a[i].first == a[j].first) {
                curr++;
            }
        }
        if (a[i].second > k) {
            continue;
        }
        if ((k - a[i].second) % 2 == 1) {
            continue;
        }
        ans = max(ans, curr);
    }
    cout << ans << endl;
}
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}