class Solution {
public:
    vector<int> dp;
    int mx;
    vector<vector<int> > arr;
    int solve(int curr){
        if(curr == arr.size()) return 0;
        int &ret = dp[curr];
        if(~ret) return ret;
        ret = INT_MAX;
        for(int j = curr, temp = -1, ss = 0 ; j < arr.size() ; j++){
            ss += arr[j][0];
            if(ss > mx) break;
            temp = max(temp, arr[j][1]);
            ret = min(ret, temp + solve(j+1));
        }
        return ret;
    }
    int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
        mx = shelf_width;
        arr = books;
        dp = vector<int>(books.size()+1, -1);
        return solve(0);
    }
};