Problem:


Score : 300 points

Problem Statement

A programming competition site AtCode provides algorithmic problems.
Each problem is allocated a score based on its difficulty.
Currently, for each integer i between 1 and D (inclusive), there are p_i problems with a score of 100i points.
These p_1 + … + p_D problems are all of the problems available on AtCode.

A user of AtCode has a value called total score.
The total score of a user is the sum of the following two elements:

Base score: the sum of the scores of all problems solved by the user.

Perfect bonuses: when a user solves all problems with a score of 100i points, he/she earns the perfect bonus of c_i points, aside from the base score (1 ≤ i ≤ D).

Takahashi, who is the new user of AtCode, has not solved any problem.
His objective is to have a total score of G or more points.
At least how many problems does he need to solve for this objective?

Constraints

1 ≤ D ≤ 10

1 ≤ p_i ≤ 100

100 ≤ c_i ≤ 10^6

100 ≤ G

All values in input are integers.

c_i and G are all multiples of 100.

It is possible to have a total score of G or more points.

Input

Input is given from Standard Input in the following format:

D G
p_1 c_1
:
p_D c_D

Output

Print the minimum number of problems that needs to be solved in order to have a total score of G or more points. Note that this objective is always achievable (see Constraints).

Sample Input 1

2 700
3 500
5 800

Sample Output 1

3

In this case, there are three problems each with 100 points and five problems each with 200 points. The perfect bonus for solving all the 100-point problems is 500 points, and the perfect bonus for solving all the 200-point problems is 800 points. Takahashi's objective is to have a total score of 700 points or more.

One way to achieve this objective is to solve four 200-point problems and earn a base score of 800 points. However, if we solve three 100-point problems, we can earn the perfect bonus of 500 points in addition to the base score of 300 points, for a total score of 800 points, and we can achieve the objective with fewer problems.

Sample Input 2

2 2000
3 500
5 800

Sample Output 2

7

This case is similar to Sample Input 1, but the Takahashi's objective this time is 2000 points or more. In this case, we inevitably need to solve all five 200-point problems, and by solving two 100-point problems additionally we have the total score of 2000 points.

Sample Input 3

2 400
3 500
5 800

Sample Output 3

2

This case is again similar to Sample Input 1, but the Takahashi's objective this time is 400 points or more. In this case, we only need to solve two 200-point problems to achieve the objective.

Sample Input 4

5 25000
20 1000
40 1000
50 1000
30 1000
1 1000

Sample Output 4

66

There is only one 500-point problem, but the perfect bonus can be earned even in such a case. 



Sample input:
2 700
3 500
5 800


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    mn = 1e5
    for i in range(1 << D):
        score = 0
        count = 0
        for j in range(D):
            if i >> j & 1 == 1:
                score += p[j] * 100 * (j+1) + c[j]
                count += p[j]
        while(score < G):
            flag = True
            for k in range(D):
                j = D - k - 1
                if i >> j & 1 == 0:
                    if score + 100*(j+1)*(p[j]-1) >= G:
                        count += math.ceil((G - score) / (100*(j+1)))
                        flag = False
                        break
                    else:
                        score += 100*(j+1)*(p[j]-1)
                        count += p[j] - 1
            if not flag:
                break
        mn = min(mn, count)
    print(mn)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]" 
    c = [int()] * (D)  # type: "List[int]" 
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

d, g = map(int, input().split())

points = [tuple(map(int, input().split())) for _ in range(d)]


points = list(map(lambda s: (s[0], s[1][0], s[1][1]), enumerate(points, 1)))

best = None

def solve(points, rest, used):
    # print(points, rest, used)
    if rest <= 0:
        return used
    if not points:
        return None

    global best
    if best and best < used:
        return None

    problem, *rests = points

    res = None
    for k in range(problem[1] + 1):
        p = k * problem[0] * 100 + (problem[2] if k == problem[1] else 0)
        tmp = solve(rests, rest - p, used + k)
        res = tmp if not res else res
        res = min(tmp, res) if tmp else res

    return res


print(solve(points, g, 0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
d,g=list(map(int,input().split()))
pc=[list(map(int,input().split())) for i in range(d)]
pp =[]
ans = []
for i in range(d):
  for j in range(pc[i][0]):
    points = (i+1)*100
    pp.append(points)
pp = np.array(pp)
arr = [0,pc[0][0]]
for i in range(1,d):
  arr.append(pc[i-1][0]+pc[i][0])
total=0
for i in range(d):
  total+=pc[i][0]
n = 2**total
for i in range(n):
  op = np.array(list(map(int,list(bin(i)[2:].zfill(total)))))
  op2 = []
  for j in range(1,len(arr)):
    f = arr[j-1]
    e = arr[j]
    op2.extend([op[f:e]])
  get_score=sum(pp*op)
  for j in range(d):
    if sum(op2[j]) == len(op2[j]):
      get_score += pc[j][1]
  ans.extend([[sum(op),get_score]])
ans.sort()
for i in ans:
  if i[1] >= g:
    print(i[0])
    break

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

D, G = map(int, input().split())
problem = {}
for i in range(D):
    pi, ci = map(int, input().split())
    problem[(i+1) * 100] = {
        'num': pi,
        'bonus': ci
    }

# 幅優先探索する
# 幅はせいぜい10択で、1番点数の高い問題を1問とるか、それ以外を全部取るか。
# それ以外の場合は深さが問題数だけ増える。
# pqueueで深さの浅い順番にpopしていく。
# (深さ, スコア, 残りの問題)

heap = []
counter = 0
heapq.heappush(heap, (0, 0, counter, problem))
memo = {}
while len(heap) > 0:
    depth, score, counter, problem = heapq.heappop(heap)
    # print(depth, score, counter, problem)
    if score >= G:
        print(depth)
        break
    for i in problem:
        tmp_problem = copy.deepcopy(problem)
        if i == max(problem.keys()):
            tmp_depth = depth + 1
            counter += 1000 ** (i // 100)
            if problem[i]['num'] == 1:
                tmp_score = score + i + problem[i]['bonus']
                del tmp_problem[i]
            else:
                tmp_score = score + i
                tmp_problem[i]['num'] -= 1
        else:
            tmp_depth = depth + problem[i]['num']
            tmp_score = score + i * problem[i]['num'] + problem[i]['bonus']
            counter += (1000 ** (i // 100)) * problem[i]['num']
            del tmp_problem[i]

        if counter not in memo:
            memo[counter] = True
            heapq.heappush(heap, (tmp_depth, tmp_score, counter, tmp_problem))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

D, G = map(int, input().split())
problem = {}
for i in range(D):
    pi, ci = map(int, input().split())
    problem[(i+1) * 100] = {
        'num': pi,
        'bonus': ci
    }

# 幅優先探索する
# 幅はせいぜい10択で、1番点数の高い問題を1問とるか、それ以外を全部取るか。
# それ以外の場合は深さが問題数だけ増える。
# pqueueで深さの浅い順番にpopしていく。
# (深さ, スコア, 残りの問題)

heap = []
counter = 0
heapq.heappush(heap, (0, 0, counter, problem))
memo = set([])
while len(heap) > 0:
    depth, score, counter, problem = heapq.heappop(heap)
    # print(depth, score, counter, problem)
    if score >= G:
        print(depth)
        break
    for i in problem:
        tmp_problem = copy.deepcopy(problem)
        if i == max(problem.keys()):
            tmp_depth = depth + 1
            counter += 1000 ** (i // 100)
            if problem[i]['num'] == 1:
                tmp_score = score + i + problem[i]['bonus']
                del tmp_problem[i]
            else:
                tmp_score = score + i
                tmp_problem[i]['num'] -= 1
        else:
            tmp_depth = depth + problem[i]['num']
            tmp_score = score + i * problem[i]['num'] + problem[i]['bonus']
            counter += (1000 ** (i // 100)) * problem[i]['num']
            del tmp_problem[i]

        if counter not in memo:
            memo.add(counter)
            heapq.heappush(heap, (tmp_depth, tmp_score, counter, tmp_problem))

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

D, G = map(int, input().split())
problem = {}
for i in range(D):
    pi, ci = map(int, input().split())
    problem[(i+1) * 100] = {
        'num': pi,
        'bonus': ci
    }

# 幅優先探索する
# 幅はせいぜい10択で、1番点数の高い問題を1問とるか、それ以外を全部取るか。
# それ以外の場合は深さが問題数だけ増える。
# pqueueで深さの浅い順番にpopしていく。
# (深さ, スコア, 残りの問題)

heap = []
counter = 0
heapq.heappush(heap, (0, 0, counter, problem))
while len(heap) > 0:
    depth, score, _, problem = heapq.heappop(heap)
    # print(depth, score, counter, problem)
    if score >= G:
        print(depth)
        break
    for i in problem:
        tmp_problem = copy.deepcopy(problem)
        if i == max(problem.keys()):
            tmp_depth = depth + 1
            if problem[i]['num'] == 1:
                tmp_score = score + i + problem[i]['bonus']
                del tmp_problem[i]
            else:
                tmp_score = score + i
                tmp_problem[i]['num'] -= 1
        else:
            tmp_depth = depth + problem[i]['num']
            tmp_score = score + i * problem[i]['num'] + problem[i]['bonus']
            del tmp_problem[i]

        already = False
        for h in heap:
            if tmp_problem == h[3]:
                already = True
        if not already:
            counter += 1
            heapq.heappush(heap, (tmp_depth, tmp_score, counter, tmp_problem))

Submission status: Time Limit Exceeded

Solution code:
d,g = map(int,input().split())
li = [list(map(int,input().split())) for i in range(d)]

for i in range(d):
  li[i].append(li[i][0]*100*(i+1) + li[i][1])
tmp = 10 ** 9
def func(x,lis,cnt):
  global tmp
  if x <= 0:
    return cnt
  else:
    for i in range(d):
      if i not in lis:
        if x <= 100*(i+1)*(li[i][0]-1):
          tmp = min(tmp,cnt + (x-1)//(100*(i+1)) + 1)
          #print("{} {} {}".format(i,lis,tmp))
        elif x <= li[i][2]:
          tmp = min(tmp,cnt + li[i][0])
          #print("{} {} {}".format(i,lis,tmp))
        else:
          tmp = min(tmp,func(x-li[i][2],lis+[i],cnt+li[i][0]))
          #print("{} {} {}".format(i,lis,tmp))
    return tmp
print(func(g,[],0))

Submission status: Time Limit Exceeded

Solution code:
d,g = map(int,input().split())
li = [list(map(int,input().split())) for i in range(d)]

for i in range(d):
  li[i].append(li[i][0]*100*(i+1) + li[i][1])
tmp = 10 ** 9
def func(x,lis,cnt):
  global tmp
  if x <= 0:
    return cnt
  else:
    for i in range(d):
      if i in lis:
        continue
      else:
        if x <= 100*(i+1)*(li[i][0]-1):
          tmp = min(tmp,cnt + (x-1)//(100*(i+1)) + 1)
          #print("{} {} {}".format(i,lis,tmp))
        elif x <= li[i][2]:
          tmp = min(tmp,cnt + li[i][0])
          #print("{} {} {}".format(i,lis,tmp))
        else:
          tmp = min(tmp,func(x-li[i][2],lis+[i],cnt+li[i][0]))
          #print("{} {} {}".format(i,lis,tmp))
    return tmp
print(func(g,[],0))

Submission status: Time Limit Exceeded

Solution code:
n, s=map(int,input().split())
q=[list(map(int, input().split())) for i in range(n)]

import numpy as np
import itertools
import pprint

bit=[0,1]

cmp=list(itertools.product(bit, repeat=n))

cp=[0]*n
qt=[0]*n
cnt=[0]*2**n

for i in range(n):
	cp[i]=100*(i+1)*q[i][0]+q[i][1]
	qt[i]=q[i][0]

for i in range(2**n):
	score=np.dot(np.array(cp),np.array(cmp[i]).T)
	cnt[i]=np.dot(np.array(qt),np.array(cmp).T)[i]
	if score<s:
		j=n-1
		while score<s and j>=0:
			if cmp[i][j]==0:
				for k in range(qt[j]):
					score+=(j+1)*100
					cnt[i]+=1
					if score>=s:
						j=0
						break
			j-=1
                
print(min(cnt))

Submission status: Time Limit Exceeded

Solution code:
n, s=map(int,input().split())
q=[list(map(int, input().split())) for i in range(n)]

import numpy as np
import itertools
import pprint

bit=[0,1]

cmp=list(itertools.product(bit, repeat=n))

cp=[0]*n
qt=[0]*n
cnt=[0]*2**n

for i in range(n):
	cp[i]=100*(i+1)*q[i][0]+q[i][1]
	qt[i]=q[i][0]

for i in range(2**n):
	score=np.dot(np.array(cp),np.array(cmp[i]).T)
	cnt[i]=np.dot(np.array(qt),np.array(cmp).T)[i]
	if score<s:
		j=n-1
		while score<s and j>=0:
			if cmp[i][j]==0:
				for k in range(qt[j]):
					score+=(j+1)*100
					cnt[i]+=1
					if score>=s:
						break
			j-=1
                
print(min(cnt))

Submission status: Time Limit Exceeded

Solution code:
def calcScore(d, g, scoreMap, index, score, solved):
    minSolved = 0
    for i in range(scoreMap[index][0] + 1):
        scoreNow = score + 100 * (index + 1) * i
        if i == scoreMap[index][0]:
            scoreNow += scoreMap[index][1]
        solvedNow = solved + i
        if scoreNow >= g:
            if minSolved == 0 or minSolved > solvedNow:
                return solvedNow
            else:
                return minSolved
        tmpSolved = 0
        if index < d - 1:
            tmpSolved = calcScore(d, g, scoreMap, index + 1, scoreNow, solvedNow)
            if minSolved == 0 or (minSolved > tmpSolved and tmpSolved != 0):
                minSolved = tmpSolved
    return minSolved


d, g = map(int, input().split())
scoreMap = [list(map(int, input().split())) for i in range(d)]

solved = calcScore(d, g, scoreMap, 0, 0, 0)

print(solved)

Submission status: Time Limit Exceeded

Solution code:
import itertools

d,g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

a = [i for i in range(d)]

b = itertools.permutations(a,d)

ans = float('inf')

for x in b:
    c = 0
    e = 0
    flag = False
    for i in x:
        for j in range(pc[i][0]):
            c += 1
            e += 100*(i+1)
            if e>=g:
                flag = True
                break
        if flag:
            break
        e += pc[i][1]
        if e >= g:
            flag = True
        if flag:
            break
    ans = min(ans, c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
d, g = list(map(int, input().split()))
ps, cs = [], []
for i in range(d):
	p, c = list(map(int, input().split()))
	ps.append(p)
	cs.append(c)

def solve(sum_score, cnt, i, ans):
	if sum_score >= g:
		return min(ans, cnt)
	elif i < d:
		for j in range(ps[i]):
			ans = solve(sum_score + 100 * (i + 1) * j, cnt + j, i + 1, ans)
		ans = solve(sum_score + 100 * (i + 1) * ps[i] + cs[i], cnt + ps[i], i + 1, ans)
	return ans

print(solve(0, 0, 0, 10 ** 10))

Submission status: Time Limit Exceeded

Solution code:
d, g = [int(i) for i in input().split()]
p = []
c = []
for i in range(d):
    x, y = [int(_) for _ in input().split()]
    p.append(x)
    c.append(y)

ans = 100 * 10
for i in range(1, 100**d):
    score = 0
    cnt = 0
    pat = [0 for i in range(d)]
    for j in range(d):
        pat[j] = i % 100
        i = i//100
    for j in range(d):
        if pat[j] >= p[j]:
            score += p[j] * (j+1) * 100 + c[j]
            cnt += p[j]
        else:
            score += pat[j] * (j+1) * 100
            cnt += pat[j]
    if score >= g and cnt < ans:
        ans = cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC104-C

D,G=map(int,input().split()) 
box=[] 
for i in range(D): 
    box.append(list(map(int,input().split()))) 
box.insert(0,[0,0]) #数を１番目に合わせるため 
info=[[0,0] for i in range(2**D)] #各全完の組での点数、解いた問題数の記憶

for i in range(2**D): #全完したものをinfoに追加
    for j in range(1,D+1): #100j点の問題は全完するか 
        if (i>>(j-1))&1: 
            info[i][0]+=box[j][1]+j*100*box[j][0] 
            info[i][1]+=box[j][0] 

for i in range(2**D):
    score=G-info[i][0]
    if score<=0:
        continue
    else:
        n=D
        while score>0:
            if (i>>(n-1))&1:
                continue
            else:
                for j in range(1,box[n][0]+1):
                    score -= 100*n
                    info[i][1]+=1 #解いた数を増やす
                    if j==box[n][0]: #ボーナス点追加
                        score-=box[n][1]
                    if  score<=0:
                        break
            n-=1
            
l=len(info)
for i in range(l-1):
    min=info[i][1]
    m=info[i]
    t=i
    for j in range(i+1,l):
        if min>info[j][1]:
            min=info[j][1]
            t=j
    info[i]=info[t]
    info[t]=m
print(info[0][1])

Submission status: Time Limit Exceeded

Solution code:

def count(P, idx, score, G, mn, cnt):
    # print(idx, score, mn, cnt)
    if score >= G and mn > cnt:
        return cnt
    if idx == 0:
        return mn
    for i in range(P[idx][0]+1):
        tmp = P[idx][1] if i == P[idx][0] else 0
        # print(idx, i)
        mn = count(P, idx-1, score+idx*100*i+tmp, G, mn, cnt+i)
    return mn

D,G = map(int, input().split())
P = [0]
for i in range(D):
    p,c = map(int, input().split())
    P.append([p,c])
print(count(P, D, 0, G, 10**9, 0))

Submission status: Time Limit Exceeded

Solution code:
def count(P, idx, score, G, mn, cnt):
    # print(idx, score, mn, cnt)
    if score >= G and mn > cnt:
        return cnt
    if idx > len(P)-1:
        return mn
    for i in range(P[idx][0]+1):
        tmp = P[idx][1] if i == P[idx][0] else 0
        # print(idx, i)
        mn = count(P, idx+1, score+idx*100*i+tmp, G, mn, cnt+i)
    return mn

D,G = map(int, input().split())
P = [0]
for i in range(D):
    p,c = map(int, input().split())
    P.append([p,c])
print(count(P, 1, 0, G, 10**9, 0))

Submission status: Time Limit Exceeded

Solution code:

def count(P, idx, score, G, mn, cnt):
    # print(idx, score, mn, cnt)
    if score >= G and mn > cnt:
        return cnt
    if idx > len(P)-1:
        return mn
    for i in range(P[idx][0]+1):
        tmp = P[idx][1] if i == P[idx][0] else 0
        # print(idx, i)
        mn = count(P, idx+1, score+idx*100*i+tmp, G, mn, cnt+i)
    return mn

D,G = map(int, input().split())
P = [0]
for i in range(D):
    p,c = map(int, input().split())
    P.append([p,c])
print(count(P, 1, 0, G, 10**9, 0))

Submission status: Time Limit Exceeded

Solution code:
D, G = [int(x) for x in input().split()]
# D < 10
# 100 <= G
#   1 <= p < 100
# 100 <= c <= 10 ** 6

# basic score: sum(solved)
# 
SPC = []
items = []

for i in range(1, D+1):
    p, c = [int(x) for x in input().split()]
    SPC.append( (100 * i, p, c))
    #for k in range(1,p): items.append((k, k * i * 100))
    #items.append((p, p * i * 100 + c))

memo = {}
def solve(SPC, i, remain):
    if (i, remain) in memo:
        return memo[(i, remain)]
    if i == len(SPC):
        return 0xffffffff
    s, p, c = SPC[i]
    m = 0xffffffff
    for j in range(0, p):
        score = s * j
        if remain - score > 0:
            m = min(m, j + solve(SPC, i+1, remain - score))
        else:
            m = min(m, j)
            break

    score = p * s + c
    if remain - score > 0:
        m = min(m, p + solve(SPC, i+1, remain - score))
    else:
        m = min(m, p)
    memo[(i, remain)] = m
    return m

print(solve(SPC, 0, G))

Submission status: Time Limit Exceeded

Solution code:
D, G = [int(x) for x in input().split()]
# D < 10
# 100 <= G
#   1 <= p < 100
# 100 <= c <= 10 ** 6

# basic score: sum(solved)
# 
SPC = []
items = []

for i in range(1, D+1):
    p, c = [int(x) for x in input().split()]
    SPC.append( (100 * i, p, c))
    #for k in range(1,p): items.append((k, k * i * 100))
    #items.append((p, p * i * 100 + c))

memo = {}

def solve(SPC, i, remain):
    if i == len(SPC):
        return 0xffffffff
    if (i, remain) in memo:
        return memo[(i, remain)]
    s, p, c = SPC[i]
    m = 0xffffffff
    for j in range(0, p):
        score = s * j
        if remain - score > 0:
            m = min(m, j + solve(SPC, i+1, remain - score))
        else:
            m = min(m, j)
    score = p * s + c
    if remain - score > 0:
        m = min(m, p + solve(SPC, i+1, remain - score))
    else:
        m = min(m, p)
    memo[(i, remain)] = m
    return m

print(solve(SPC, 0, G))

Submission status: Time Limit Exceeded

Solution code:
difficulties, goal = map(int, input().split())

pcs = [list(map(int, input().split())) for _ in range(difficulties)]

dp = [[0] * 1102 for _ in range(difficulties + 1)]

for d, pc in enumerate(pcs, 1):
    problem, complete = pc

    score = [x*100*d for x in range(problem)] + [problem*100*d+complete] +[0] * 1001

    for i in range(1, 1001):
        for j in range(0, i + 1):
            if i - j > problem:
                dp[d][i] = max(dp[d][i], dp[d - 1][j])
            else:
                dp[d][i] = max(dp[d][i], dp[d-1][j] + score[i-j])

for i, a in enumerate(dp[difficulties]):
    if a >= goal:
        print(i)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys


if __name__ == '__main__':
    D, G = map(int, input().split())
    # pc_list = [list(map(int,input().split())) for i in range(D)]

    p = ['-1'] * D
    c = ['-1'] * D

    for i in range(D):
        p[i], c[i] = map(int, input().split())

    if D == 1:
        my_list = list(itertools.product(range(p[0]+1)))
    elif D == 2:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1)))
    elif D == 3:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1)))
    elif D == 4:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1)))
    elif D == 5:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1), range(p[4]+1)))
    elif D == 6:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1), range(p[4]+1), range(p[5]+1)))
    elif D == 7:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1), range(p[4]+1), range(p[5]+1), range(p[6]+1)))
    elif D == 8:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1), range(p[4]+1), range(p[5]+1), range(p[6]+1), range(p[7]+1)))
    elif D == 9:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1), range(p[4]+1), range(p[5]+1), range(p[6]+1), range(p[7]+1), range(p[8]+1)))
    elif D == 10:
        my_list = list(itertools.product(range(p[0]+1),range(p[1]+1), range(p[2]+1), range(p[3]+1), range(p[4]+1), range(p[5]+1), range(p[6]+1), range(p[7]+1), range(p[8]+1), range(p[9]+1)))

    min_count = sys.maxsize
    for e in my_list:
        e_list = list(e)
        score = 0
        for i in range(len(e_list)):
            score += (i+1)*100*e_list[i]
            if e[i] == p[i]:
                score += c[i]
        count = sum(e_list)
        if score >= G and min_count > count:
            min_count = count
    print(min_count)

Submission status: Time Limit Exceeded

Solution code:
D, G = [int(i) for i in input().split()]
pc = [list(map(lambda x: int(x), input().split())) for i in range(D)]
pc.insert(0,[])
ans = float('inf')

def f(score, i, kaitousu):
	global ans
	if i <= D:
		for j in range(pc[i][0] + 1):
			if j == pc[i][0]:
				newScore = score + 100 * i * j + pc[i][1]
			else:
				newScore = score + 100 * i * j
			newKaitousu = kaitousu + j
			if newScore >= G:
				if newKaitousu < ans:
					ans = newKaitousu
				break
			else:
				f(newScore, i + 1, newKaitousu)

f(0, 1, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
D, G = list(map(int, input().split()))

G /= 100
l = [[0]*3 for i in range(D)]

for i in range(D):
    p, c = list(map(int, input().split()))
    l[i][0] = i+1
    l[i][1] = p
    l[i][2] = c/100

l = sorted(l, key=lambda x: x[0], reverse=True)


def dfs(i, scores):
    if scores <= 0:
        return 0

    if i == D:
        return 1e9

    a, p, b = l[i]

    counts = [1e9]*(p+1)
    for j in range(p+1):
        if j == p:
            counts[j] = dfs(i+1, scores-a*p-b) + p
        elif scores-a*j >= 0:
            counts[j] = dfs(i+1, scores-a*j) + j

    ans = min(counts)
    return ans


ans = dfs(0, G)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
 
 
def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    def calc(order):
        res = 0
        rest = G
        for i in order:
            each = (i + 1) * 100
            if rest <= each * p[i]:
                res += rest // each
                if rest % each > 0:
                    res += 1
                break
            else:
                res += p[i]
                rest -= each * p[i] + c[i]
                if rest <= 0:
                    break
        return res
 
    def dfs(cur, used):
        ret = float('inf')
        if len(cur) == D:
            tmp = calc(cur)
            return tmp
        for i, u in enumerate(used):
            if not u:
                used[i] = True
                ret = min(ret, dfs(cur + [i], used))
                used[i] = False
        return ret
 
    used = [False] * D
    ret = dfs([], used)
    print(ret)
    return
 
 
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]" 
    c = [int()] * (D)  # type: "List[int]" 
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    def calc(order):
        res = 0
        rest = G
        for i in order:
            each = (i + 1) * 100
            if rest <= each * p[i]:
                res += rest // each
                if rest % each > 0:
                    res += 1
                break
            else:
                res += p[i]
                rest -= each * p[i] + c[i]
                if rest <= 0:
                    break
        return res

    def dfs(cur, used):
        ret = float('inf')
        if len(cur) == D:
            tmp = calc(cur)
            return tmp
        for i, u in enumerate(used):
            if not u:
                used[i] = True
                ret = min(ret, dfs(cur + [i], used))
                used[i] = False
        return ret

    used = [False] * D
    ret = dfs([], used)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]" 
    c = [int()] * (D)  # type: "List[int]" 
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(D, G, p, c)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
d,g=map(int,input().split())
g=g//100
p_list=[0]
c_list=[0]
for i in range(d):
    p,c=map(int,input().split())
    p_list.append(p)
    c_list.append(c//100)
dp=[]
for i in range(d+1):
    sub_list=[]
    for j in range(g+1):
        sub_list.append(10**9)
    dp.append(sub_list)
dp[0][0]=0
for i in range(1,d+1):
    for j in range(g+1):
        for k in range(p_list[i]+1):
            if k==p_list[i]:
                if j-i*k-c_list[i]>=0:
                    dp[i][j]=min(dp[i][j],dp[i-1][j-i*k-c_list[i]]+k)
                else:
                    dp[i][j]=min(dp[i][j],dp[i-1][0]+k)
            else:
                if j-i*k>=0:
                    dp[i][j]=min(dp[i][j],dp[i-1][j-i*k]+k)
                else:
                    dp[i][j]=min(dp[i][j],dp[i-1][0]+k)
print(dp[d][g])

Submission status: Time Limit Exceeded

Solution code:
#3
d,g = map(int,input().split())
lista = []
for i in range(d):
    lista.append([])
    p,c = map(int,input().split())
    lista[i] = [p,c]
    
def search(allcomp,notouch,touch,rem,toachiev,ps):
    #allcomp 全部解く
    #notouch 触らない
    #touch 触る
    #残りの選択肢
    #達成までに必要な得点
    #ここまで解いてる問題数
    if touch != []:
        #print(allcomp,notouch,touch,rem,toachiev,ps)
        point = (touch[0] + 1)*100
        problems = lista[touch[0]][0]
        vnus =  lista[touch[0]][1]
        #print(point,problems,vnus)
        if toachiev == 0:
            return ps
        else:
            needproblems = toachiev//point
            if toachiev%point != 0:
                needproblems += 1
                
            if needproblems<=problems:
                return ps+needproblems
            else:
                if point*problems + vnus >= toachiev:
                    return ps+problems
                else:
                    return 10**9
                
    else:
        if len(rem)==1:
            if toachiev == 0:
                return ps
            else:
                rempoint = (rem[0] + 1)*100
                notouchpoint_max = 0
                if notouch != []:
                    notouchpoint_max = (max(notouch) + 1)*100

                if notouchpoint_max <= rempoint:
                    return search(allcomp,notouch,rem,[],toachiev,ps)
                else:
                    return 10**9
        else:
            if toachiev == 0:
                return ps
            else:
                minp = 10**9
                for i in range(len(rem)):
                    allcomp_t,notouch_t,rem_t,toachiev_t,ps_t = list(allcomp),list(notouch),list(rem),toachiev,ps
                    notouch_t.append(rem[i])
                    rem_t = rem[:i]+rem[i+1:]
                    case1 = search(allcomp_t,notouch_t,[],rem_t,toachiev_t,ps_t)
                    
                    if minp > case1:
                        minp = case1
                        
                    if minp > ps:
                        allcomp_t,notouch_t,rem_t,toachiev_t,ps_t = list(allcomp),list(notouch),list(rem),toachiev,ps
                        allcomp_t.append(rem[i])
                        rem_t = rem[:i]+rem[i+1:]
                        toachiev_t = toachiev_t - (rem[i] + 1)*100*lista[rem[i]][0] - lista[rem[i]][1]
                        if toachiev_t <0:
                            toachiev_t = 0
                        ps_t = ps_t + lista[rem[i]][0]
                        case2 = search(allcomp_t,notouch_t,[],rem_t,toachiev_t,ps_t)
                        
                        if minp > case2:
                            minp = case2
                    
            return minp
                
        
        
        
        
makerem = []
for i in range(d):
    makerem.append(i)
    
print(search([],[],[],makerem,g,0))