abc 104 c All Green (python)

ずっとほったらかしていた問題。
dfs で全探索するのだけど、愚直に計算すると間に合わない。
• 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。
• 中途半端に解く配点があるなら、それは完全に解く配点以外の配点の中で最も高い配点である。
の２点に気づいて探索する候補を絞る必要がある。

実装は dfs(a,b,c,d) として、
a = 今解こうとしている配点
b = 今まで解いた問題の配点の総和
c = 今まで解いた問題数
d = 中途半端に解いたことがあるか
で全探索した。２つ目の条件を上手く満たすように配点を高い順に a を調べた。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**7)

n,k = list(map(int,readline().split()))
k //= 100
l = []
for i in range(n):
  array = list(map(int,readline().split()))  
  l.append(array)

ans = float('inf')

def f(a,b,c,d):
  global ans
  if a == 0:
    if b >= k:
      ans = min(ans,c)
    return
  if c >= ans:
    return
  if b >= k:
    ans = min(ans,c)
    return
  else:
    if d == 0:
      g = min(l[a-1][0],(k-b)//a+2)
      return [f(a-1,b+a*i,c+i,1) for i in range(1,g)],f(a-1,b,c,d),f(a-1,b+a*(l[a-1][0])+(l[a-1][1])//100,c+l[a-1][0],d)
    else:
      return f(a-1,b,c,d),f(a-1,b+a*(l[a-1][0])+(l[a-1][1])//100,c+l[a-1][0],d)
    
  
f(n,0,0,0)
print(ans)