思路与算法

假定最右走到第i栋楼。至少要向右跳i-1次，每栋可先取得一件物品；剩余m-(i-1)步用于取得额外楼层的物品。第j栋还有h_j-1件同价值物品可选，因此只需在前i栋的这些物品中选择价值最高的至多m-i+1件。

这个抽象确实可实现。进入一栋楼时不论落在哪一层，都能沿“逐层向上，顶层滑到一层，再逐层向上”的环依次访问所有楼层，前k次环上移动恰好获得k件新物品。选定本楼要额外取的数量后沿该环走完，再跳到右楼即可，不需要返回已处理的楼。

按前缀从左到右枚举，用小根堆存已选额外物品的(价值,数量)，并维护已选件数和价值和。遇到新楼，把正价值的h_i-1件作为一个堆结点加入；预算每前进一楼减少1，超出时从堆顶删掉最低价值物品，可一次删掉一批相同价值。答案取“已到达楼栋首件价值和+堆内额外价值和”的最大值。非正价值物品可不拿，因题目说拿取不耗时且求最大值。

原题没有给m和v_i的数值上限。m超过Σh_i-1时不会增加可取得物品，输入时可精确夹到10^12（由n,h_i≤10^6推出的总楼层上界）；价值本身以及价值和使用动态多精度整数，乘法只需乘楼层数量。

正确性说明

对任何实际路线，设最右到达第i楼。每个1..i楼必然访问，至少花i-1次跨楼移动。把各楼第一次到达时的那件物品列为首件，其余每件新物品都必须在另外一次移动后取得；因此额外物品总数至多m-i+1，且第j楼最多有h_j-1件。把首件都计为正价值最大收益只会提高路线的上界。故实际路线价值不超过该前缀首件和加预算内最高价值额外物品之和。

反过来，任意满足各楼数量上限与总预算的额外物品选择都可按从左到右实现：每次进入楼后，使用上行与顶层滑梯构成的环，连续走选定数量的步，每步都访问一个此前未取的本楼楼层；再向右跳一次。总用时恰为i-1加额外件数，不超过m。因此上述上界可达。

固定前缀时，从已选物品中删除最便宜者会保留给定预算下价值最高的集合。加入新楼后再次删除至符合预算即可保持此不变式。被丢弃的物品以后不必恢复，因为后续预算只会减少，新增物品只可能挤掉更便宜者，不会使曾被丢弃者重新进入最优集合。对所有可到达前缀取最大值，得到全局最优。

复杂度

设输入所有价值数字的总位数为D，单个价值及答案的最大位数为L（加上至多12位的数量增长）。堆结点至多n个，每个批次加入一次、完整弹出至多一次；预算缩减导致的部分批次删除每楼至多一次。因此共O(n log n)次堆比较及O(n)次大整数加减/小整数乘法，计入数字运算为O(D+nL log n)时间、O(D+nL)的宽松空间上界；实际只保存可选前缀中的堆值，输入逐行处理。m的读取夹值为O(输入m位数)，不按m循环。初始化为常数，不展开Σh_i个物品。

易错点

初始位于第一楼顶层，已有一件可以直接取得，所以预算是m-i+1而非m-i。到较高楼时会落在相同层，但环构造仍能用每步一个新楼层的代价取得任意数量，不能错误地额外收取回顶楼的时间。不能把每层都建成一个堆结点，Σh_i可达10^12；使用带数量的批次。预算递减时要同步删堆、件数和价值。初始或途经非正价值物品可不拿。数据使用公开样例及独立构造训练数据，不是官方原始评测数据。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Big {
    vector<unsigned> a;
    Big(unsigned x = 0) {
        if (x)
            a.push_back(x);
    }
    Big(string s) {
        for (int p = (int)s.size(); p > 0; p -= 9) {
            int l = max(0, p - 9);
            a.push_back(stoul(s.substr(l, p - l)));
        }
        while (!a.empty() && !a.back())
            a.pop_back();
    }
    void add(const Big &b) {
        unsigned long long carry = 0;
        for (size_t i = 0; i < max(a.size(), b.a.size()) || carry; i++) {
            if (i == a.size())
                a.push_back(0);
            unsigned long long x = a[i] + carry + (i < b.a.size() ? b.a[i] : 0);
            a[i] = x % 1000000000;
            carry = x / 1000000000;
        }
    }
    void sub(const Big &b) {
        long long carry = 0;
        for (size_t i = 0; i < a.size(); i++) {
            long long x = (long long)a[i] - (i < b.a.size() ? b.a[i] : 0) - carry;
            carry = x < 0;
            if (carry)
                x += 1000000000;
            a[i] = x;
        }
        while (!a.empty() && !a.back())
            a.pop_back();
    }
    Big mul(unsigned x) const {
        Big b;
        unsigned long long carry = 0;
        for (unsigned v : a) {
            unsigned long long z = (unsigned long long)v * x + carry;
            b.a.push_back(z % 1000000000);
            carry = z / 1000000000;
        }
        if (carry)
            b.a.push_back(carry);
        while (!b.a.empty() && !b.a.back())
            b.a.pop_back();
        return b;
    }
    bool operator<(const Big &b) const {
        if (a.size() != b.a.size())
            return a.size() < b.a.size();
        for (int i = (int)a.size() - 1; i >= 0; i--)
            if (a[i] != b.a[i])
                return a[i] < b.a[i];
        return false;
    }
    string str() const {
        if (a.empty())
            return "0";
        string s = to_string(a.back());
        for (int i = (int)a.size() - 2; i >= 0; i--) {
            string t = to_string(a[i]);
            s += string(9 - t.size(), '0') + t;
        }
        return s;
    }
};
struct Item {
    Big v;
    unsigned count;
};
struct Greater {
    bool operator()(const Item &a, const Item &b) const {
        return b.v < a.v;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string ms;
    cin >> n >> ms;
    unsigned long long m = 0;
    for (char c : ms)
        if (c >= '0' && c <= '9')
            m = min(1000000000000ULL, m * 10 + (c - '0'));
    priority_queue<Item, vector<Item>, Greater> heap;
    unsigned long long selected = 0;
    Big base, sum, best;
    for (int i = 0; i < n; i++) {
        unsigned h;
        string vs;
        cin >> h >> vs;
        if ((unsigned long long)i > m)
            continue;
        bool positive = !vs.empty() && vs[0] != '-';
        if (vs[0] == '+')
            vs.erase(vs.begin());
        if (!positive)
            continue;
        Big v(vs);
        base.add(v);
        if (h > 1 && !v.a.empty()) {
            heap.push({v, h - 1});
            selected += h - 1;
            sum.add(v.mul(h - 1));
        }
        unsigned long long budget = m - i;
        while (selected > budget) {
            Item x = heap.top();
            heap.pop();
            unsigned take = (unsigned)min<unsigned long long>(x.count, selected - budget);
            sum.sub(x.v.mul(take));
            selected -= take;
            x.count -= take;
            if (x.count)
                heap.push(x);
        }
        Big now = base;
        now.add(sum);
        if (best < now)
            best = now;
    }
    cout << best.str() << '\n';
}