Здравствуйте! Решение не такое запутанное, как в "27-110_99ballov.py" и интуитивнее, чем ДП в целом, как мне кажется.
n = None
k = None
buff = []
with open("27-110b.txt") as f:
n, k = map(int, f.readline().split())
buff.append((k, 0))
for i, x in enumerate(f):
a, b = list(map(int, x.split()))
buffT = []
for case in buff:
buffT.append(case)
buffT.append((k, case[1] + b))
if case[0] > 0: buffT.append((case[0] - 1, case[1] + a))
buff = []
buffT.sort(key=lambda x: (-x[1], -x[0]))
border = None
for case in buffT:
if not border or case[0] > border:
buff.append(case)
border = case[0]
buff.sort(key=lambda x: (-x[1], x[0]))
print(buff[0][1])
И бонусом ДП без лишних больших массивов, дополнительных итераций и с поточной обработкой (вдруг пригодится кому):
n = None
k = None
res = []
with open("27-110b.txt") as f:
n, k = map(int, f.readline().split())
res = [[0] * (k + 1) for i in range(2)]
for i, x in enumerate(f):
a, b = list(map(int, x.split()))
for j in range(k + 1):
res[1][j] = max(res[0][j],
a + res[0][j - 1] if j
else b + max(res[0]))
res[0], res[1] = res[1], res[0]
print(max(res[0]))