class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n = days.size();
        vector<int> dp(n+1,0);
        dp[n-1] = min(costs[0],min(costs[1],costs[2]));
        for(int i=n-2;i>=0;i--)
        {
            int pos1 = upper_bound(days.begin(),days.end(),days[i])-days.begin();
            int pos2 = upper_bound(days.begin(),days.end(),days[i]+6)-days.begin();
            int pos3 = upper_bound(days.begin(),days.end(),days[i]+29)-days.begin();
            int cost1 = costs[0]+dp[pos1];
            int cost2 = costs[1]+dp[pos2];
            int cost3 = costs[2]+dp[pos3];
            dp[i] = min(cost1,min(cost2,cost3));
        }
        return dp[0];
    }
};