def main():
    N, M = [int(i) for i in input().split()]
    values = [[int(i) for i in input().split()] for _ in range(N)]
    values.append([0, 0])
    
    # best buy without sell at month 0
    bests = {0: values[0][0]}

    for i in range(len(values)):
        for j in range(i-M, i):
            if j in bests.keys():
                if i not in bests.keys():
                    bests[i] = bests[j] - values[j][i-j] + values[i][0]
                else:
                    bests[i] = min(bests[j] - values[j][i-j]+ values[i][0], bests[i])

    print(bests[N])


main()