def minPathCose(cost, m, n) :
    x = minPathCost(cost, m-1, n)
    y = minPathCost(cost, m, n-1)
    return getMin(x, y) + cost[m][n];

def getMin(a, b) :
    return a if a < b else b 

def minPathCost(cost, m, n) :
    if m == 0 && n == 0 : return cost[0][0]
    if m == 0 : return minPathCost(cost, 0, n-1) + cost[0][n]
    if n == 0 : return minPathCost(cost, m-1, 0) + cost[m][0]

    x = minPathCost(cost, m-1, n)
    y = minPathCost(cost, m, n-1)
    return getMin(x, y) + cost[m][n];

def getMin(a, b) :
    return a if a < b else b 

def minPathCost(cost, m, n) :
    # 이미 캐싱
    if MEM[m][n] != 0 : return MEM[m][n]

    if m == 0 && n == 0 : return cost[0][0]
    elif m == 0 : return minPathCost(cost, 0, n-1) + cost[0][n]
    elif n == 0 : return minPathCost(cost, m-1, 0) + cost[m][0]
    else :
        x = minPathCost(cost, m-1, n)
        y = minPathCost(cost, m, n-1)
        MEM[m][n] = getMin(x, y) + cost[m][n]
    
    return MEM[m][n]

def getMin(a, b) :
    return a if a < b else b 

def minPathCost(cost, m, n) :
    # 이미 캐싱
    MEM[0][0] = cose[0][0]

    for j in range (1, N) :
        MEM[0][j] = MEM[0][j-1] + cost[0][j]

    for i in range (1, N) :
        MEM[i][0] = MEM[i-1][0] + cost[i][0]
    
    for i in range(1, M):
        for j in range(1, N) :
            MEM[i][j] = getMin(MEM[i-1][j], MEM[i][j-1]) + cost[i][j];
    
    return MEM[M-1][N-1];

def countWays(n) :
    if n == 1 : return 1
    if n == 2 : return 2

    return countWays(n-1) + countWays(n-2)

def waysToScore(n):
    if n < 0 : return 0
    if n == 0 : return 1
    return waysToScore(n-10) + waysToScore(n-5) + waysToScore(n-3)

def waysToScore(n):
    arr = [0] * n
    arr[0] = 1

    for i in ranger(1, n) :
        if i -3 >= 0 : arr[i] += arr[i-3]
        if i -5 >= 0 : arr[i] += arr[i-5]
        if i -10 >= 0 : arr[i] += arr[i-10]
    return arr[n]

def maxSubArraySum(arr, n) :
    maxSum = 0
    tempSum = 0

    for i in range(n):
        tempSum = 0
        for j in range(i,n):
            tempSum += arr[j]
            if (tempSum > maxSum) : maxSum = tempSum
    
    return maxSum

def maxSubArraySum(arr, n) :
    maxSumSoFar = 0
    maxSumEndingHere = 0

    for i in range(n):
        maxSumEndingHere += arr[i];
        if maxSumEndingHere < 0 : maxSumEndingHere = 0
        if maxSumEndingHere > maxSumSoFar : 
            maxSumSoFar = maxSumEndingHere

    return maxSumSoFar