class Solution:
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        #FIRST METHOD N^2 DP
        # THE METHOD IS O(N)
        if sum(gas) < sum(cost):
            return -1
        n = len(gas)
        sum_num = 0
        index = -1
        for i in range(n):
            sum_num += gas[i]-cost[i]
            if sum_num <0:
                index = i
                sum_num = 0
        return index+1