def solve(priceList):
    floors = len(priceList)
    frequencies = len(priceList[0])
    dp = [[0] * frequencies for _ in range(floors)]
    for j in range(frequencies):
        dp[0][j] = priceList[0][j]
    for i in range(1, floors):
        for j in range(frequencies):
            min_cost = float('inf')
            for k in range(frequencies):
                if k != j: 
                    min_cost = min(min_cost, dp[i-1][k])
            dp[i][j] = priceList[i][j] + min_cost
    return min(dp[-1])

def getUnallottedUsers(bids, totalShares):
    sorted_bids = sorted(bids, key=lambda x: (-x[2], x[3]))
    
    allocated_shares = {}
    unallotted_users = set()
    remaining_shares = totalShares
    
    for user_id, shares, price, timestamp in sorted_bids:
        if remaining_shares == 0:
            unallotted_users.add(user_id)
            continue
        
        allocated = min(shares, remaining_shares)
        allocated_shares[user_id] = allocated_shares.get(user_id, 0) + allocated
        remaining_shares -= allocated
        
        if allocated_shares[user_id] < shares:
            unallotted_users.add(user_id)
    
    fully_unallotted = [user_id for user_id, shares in allocated_shares.items() if shares == 0]
    fully_unallotted.extend([bid[0] for bid in bids if bid[0] not in allocated_shares])
    
    return sorted(set(fully_unallotted))

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int MOD = 1e9 + 7;
class SegmentTree {
    vector<int> tree;
    vector<int> arr;
    int size;

    void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(2 * node, start, mid);
            build(2 * node + 1, mid + 1, end);
            tree[node] = min(tree[2 * node], tree[2 * node + 1]);
        }
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || l > end) return INT_MAX;
        if (l <= start && end <= r) return tree[node];
        int mid = (start + end) / 2;
        return min(query(2 * node, start, mid, l, r), query(2 * node + 1, mid + 1, end, l, r));
    }

public:
    SegmentTree(const vector<int>& input) : arr(input), size(input.size()) {
        tree.resize(4 * size);
        build(1, 0, size - 1);
    }

    int query(int l, int r) {
        return query(1, 0, size - 1, l, r);
    }
};
long long maxProfitSubstring(const string& str, const vector<int>& values) {
    int n = str.size();
    vector<int> prefixSum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefixSum[i + 1] = prefixSum[i] + values[str[i] - 'a'];
    }
    vector<int> indexArray(n);
    for (int i = 0; i < n; ++i) {
        indexArray[i] = str[i] - 'a' + 1; 
    }
    SegmentTree segTree(indexArray);
    long long maxProfit = 0;
    for (int start = 0; start < n; ++start) {
        for (int end = start; end < n; ++end) {
            int minIndex = segTree.query(start, end);
            long long sum = prefixSum[end + 1] - prefixSum[start];
            long long profit = sum * minIndex;
            maxProfit = max(maxProfit, profit);
        }
    }

    return maxProfit % MOD;
}

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

vector<int> tree;

void update(int start, int end, int parent, long long index){
   if (start > end) {
       return;
   }
   if (start == end) {
       tree[parent]++;
       return;
   }
   int mid = (start + end) / 2;
   if (index > mid) {
       update(mid + 1, end, 2 * parent + 2, index);
   }
   else {
       update(start, mid, 2 * parent + 1, index);
   }
   tree[parent] = tree[2 * parent + 1] + tree[2 * parent + 2];
}

int query(int start, int end, int parent, int qstart, int qend){
   if (qstart > end || qend < start) {
       return 0;
   }
   if (qstart <= start && qend >= end) {
       return tree[parent];
   }
   int mid = (start + end) / 2;
   int L = query(start, mid, 2 * parent + 1, qstart, qend);
   int R = query(mid + 1, end, 2 * parent + 2, qstart, qend);
   return L + R;
}

int solve(string &S){
   int n = S.size();
   tree.resize(4 * 2 * n + 1, 0);

   int shift = n;
   long long currSum = 0;
   long long cnt = 0;

   update(0, 2 * n, 0, 0 + shift);
  
   for (int i = 0; i < n; i++) {
       currSum += (S[i] == '1' ? 1 : -1);
     
       int lessThan = (currSum + shift) - 1;
       cnt += query(0, 2 * n, 0, 0, lessThan);

       update(0, 2 * n, 0, currSum + shift);
   }
   return cnt;
}