class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& cost) {
        int n=cost.size();
        vector <int> dp(n+1,1e8);
        dp[0]=0;
        for (int i=0;i<n;i++)
        {
            for (int j=n;j>=1;j--)
            {
                dp[j]=min(dp[j-1]+cost[i][0],dp[j]+cost[i][1]);
            }
            dp[0]=dp[0]+cost[i][1];
        }
        return dp[n/2];
    }
};