Problem 60: Job Scheduling with Deadlines (Bitmask DP)

Problem Statement: Given n jobs each with a deadline and profit, schedule them such that no two jobs overlap and maximize total profit. Use bitmask dynamic programming to solve for n up to 20.

Input

The first line contains an integer n. Each of the next n lines contains two integers: deadline and profit.

Output

Print the maximum profit achievable by scheduling a subset of jobs.

Examples


Input:
4
4 70
2 60
4 50
3 40

Output:
120

Solution Explanation

With n up to 20, bitmask DP is feasible. Each state represents a subset of jobs taken. Validate feasibility (jobs must complete before their deadlines) and maximize profit.

Solution in C++


#include 
#include 
#include 
using namespace std;

struct Job { 
    int d, p; 
};

int main(){
    int n; 
    cin >> n;
    vector jobs(n);
    for(int i = 0; i < n; i++){
        cin >> jobs[i].d >> jobs[i].p;
    }
    int N = 1 << n;
    vector dp(N, 0);
    vector timeUsed(N, 0);
    for(int mask = 0; mask < N; mask++){
        for(int j = 0; j < n; j++){
            if(!(mask & (1 << j))){
                int next = mask | (1 << j);
                if(timeUsed[mask] + 1 <= jobs[j].d){
                    dp[next] = max(dp[next], dp[mask] + jobs[j].p);
                    timeUsed[next] = max(timeUsed[next], timeUsed[mask] + 1);
                }
            }
        }
    }
    int ans = 0;
    for(auto x : dp) ans = max(ans, x);
    cout << ans << "\n";
    return 0;
}