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:
from itertools import *
from math import *

D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
seq = list(range(D))
x = list(permutations(seq, D))
#print(x)
ans = float("inf")
G2=G
for cand in x:
    cnt = 0
    G=G2
    for ind in cand:
        probpoint = (ind + 1) * 100
        if G<=0:
            break
        if G <= probpoint * (probs[ind][0] - 1):
            cnt = cnt + ceil(G / probpoint)
            G=G-probpoint*ceil(G / probpoint)
        else:
            cnt=cnt+probs[ind][0]
            G=G-(probpoint * probs[ind][0]+probs[ind][1])
    ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
from math import *

D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
seq = list(range(D))
x = list(permutations(seq, D))
#print(x)
ans = float("inf")
G2=G
for i in range(len(x)):
    cand = x[i]
    cnt = 0
    G=G2
    for j in range(D):
        ind = cand[j]
        probpoint = (ind + 1) * 100
        if G<=0:
            break
        if G <= probpoint * (probs[ind][0] - 1):
            cnt = cnt + ceil(G / probpoint)
            G=G-probpoint*ceil(G / probpoint)
        else:
            cnt=cnt+probs[ind][0]
            G=G-(probpoint * probs[ind][0]+probs[ind][1])
    ans=min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
cos_per = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    #cos_per.append([d+1,sum(tmp)/p])
    cos_per.append([d+1,d+1])
#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-最小でいくつの問題セットを必要とするか-#
tmp = 0
j=0
for i in range(len(maxScore)-1,-1,-1):
    j+=1
    tmp += maxScore[i]
    if tmp >= G:
        min_num = j
        break
#-最小-2個はスコアが高いものを入れてよし-#
#cos_per.sort(key = lambda x:-x[1])
choice = set(range(1,D+1))
#choiceList = []
#for i in range(0,min_num-3):
 #   choiceList+=score[cos_per[i][0]-1]
 #   choice.discard(cos_per[i][0])
 #   max_num -=1
 
#-足し上げる-#

ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    times = 0
    total = 0
    flag = 0
    for ci in ch:
        for sc in score[ci-1]:
            total += sc
            times += 1
            if total >= G:
                ans = min(ans,times)
                falg = 1
                break
    if flag ==1:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
cos_per = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    cos_per.append([d+1,sum(tmp)/p])
#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-最小でいくつの問題セットを必要とするか-#
tmp = 0
j=0
for i in range(len(maxScore)-1,-1,-1):
    j+=1
    tmp += maxScore[i]
    if tmp >= G:
        min_num = j
        break
#-最小-1個はコスパが高いものを入れてよし-#
#cos_per.sort(key = lambda x:-x[1])
#choice = set(range(1,D+1))
#choiceList = []
#for i in range(min_num-1):
 #   choiceList+=score[cos_per[i][0]-1]
 #   choice.discard(cos_per[i][0])
 #   max_num -=1
#-足し上げる-#
choice = set(range(1,D+1))
ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    tmp = []
    for ci in ch:
        tmp+=score[ci-1]
    times = 0
    total = 0
    for sc in tmp:
        total += sc
        times += 1
        if total >= G:
            ans = min(ans,times)
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

D, G = map(int, input().strip().split())
p = list()
c = list()
for _ in range(D):
    tmp_p, tmp_c = map(int, input().strip().split())
    p.append(tmp_p)
    c.append(tmp_c)

def min_problem(res, score, i):
    if i == D - 1:
        j = 0
        while j < p[i] and score < G:
            j += 1
            res += 1
            score += 100 * (i+1)
        if j == p[i]:
            score += c[i]
        if score < G:
            return -1, -1
        else:
            return res, score
    res_1, score_1 = min_problem(res, score, i + 1)
    for j in range(1,p[i]+1):
        res_2, score_2 = min_problem(res + j,
                                    score + j * 100 * (i+1),
                                    i + 1)
        if res_1 > res_2 or res_1 == -1:
            res_1 = res_2
            score_1 = score_2
    res_2, score_2 = min_problem(res + p[i],
                                 score + p[i] * 100 * (i+1) + c[i],
                                 i + 1)
    if res_1 > res_2 or res_1 == -1:
        return res_2, score_2
    else:
        return res_1, score_1

res = 0
score = 0
i = 0
res, score = min_problem(res, score, i)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

import math
import sys
input = sys.stdin.readline

D, G = map(int, input().split())
# print(D, G)
P = []
C = []
for i in range(D):
    p,  c = map(int, input().split())
    P.append(p)
    C.append(c)

INF = 10**15


def F(i, n, GetPoint):
    if i == D:
        if GetPoint >= G:
            return n, GetPoint
        else:
            return INF, INF

    PerPoint = (i+1)*100

    if GetPoint < G:
        temp = INF, INF
        for j in range(P[i]+1):
            if j != P[i]:
                N, GP = F(i+1, n+j, GetPoint+j*PerPoint)
            else:
                N, GP = F(i+1, n+j, GetPoint+j*PerPoint + C[i])
            if N < temp[0]:
                temp = N, GP
        return temp
    else:
        return n, GetPoint


print(F(0, 0, 0)[0])

Submission status: Time Limit Exceeded

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

def dfs(s=[], score=0):
    ans = float('inf')
    if len(s)==d:
        if score >= g:
            return sum(s)
        else:
            return float('inf')
    else:
        p, c = pc[len(s)]
        for i in range(p+1):
            a = 100*(len(s)+1)*i
            if i==p:
                a+=c
            ans = min(ans, dfs(s+[i], score+a))
    return ans

print(dfs([]))

Submission status: Time Limit Exceeded

Solution code:
d,g = map(int,input().split())
P = [0]*d
C = [0]*d
for i in range(d):
  P[i],C[i] = map(int,input().split())
  
x = 10**4
INF = 10**10
dp = [[INF]*(g//100+x) for _ in range(d+1)]
dp[0][0]=0

for i in range(1,d+1):
  for k in range(g//100+x):
      dp[i][k] = min(dp[i][k],dp[i-1][k])
  
      for j in range(P[i-1]):    
        q = j+1
        score = q*i        
        if q == P[i-1]:
          score += C[i-1]//100    
    
        if k - score >= 0:
          dp[i][k] = min(dp[i][k],dp[i-1][k-score]+q)      
        
print(min(dp[-1][g//100:]))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())

a = []
for i in range(n):
    a.append(list(map(int,input().split())))

b = []
for i in range(n):
    b += [100 * (i + 1) for j in range(a[i][0])]

d = []
ans = 1000000000000000
for i in range(2 ** len(b)):
    check = 0
    c = []
    counter = {}
    for j in range(len(b)):
        if (i >> j) & 1:
            if b[j] in counter.keys():
                c.append(b[j])
                counter[b[j]] += 1
            else:
                c.append(b[j])
                counter[b[j]] = 1
    for k in range(n):
        if 100 * (k + 1) in counter.keys():
            if counter[100 * (k + 1)] == a[k][0]:
                check += a[k][1]
    check += sum(c)
    if check >= m and len(c) < ans:
        ans = len(c)
    #print(ans, check, c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())

a = []
for _ in range(n):
    a.append(list(map(int,input().split())))

b = []
for i in range(n):
    b += [100 * (i + 1) for j in range(a[i][0])]
#print(b)

d = []
ans = 1000000000000000
for i in range(2 ** len(b)):
    check = 0
    c = []
    for j in range(len(b)):
        if (i >> j) & 1:
            c.append(b[j])
    for k in range(n):
        if c.count(100 * (k + 1)) == a[k][0]:
            check += a[k][1]
    #print(check)
    check += sum(c)
    if check >= m and len(c) < ans:
        ans = len(c)
    #print(ans, check, c)
    
    d.append(c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
def main():
    d, g = map(int, input().split())
    score_set = []
    score_set_qnum = []
    for i1 in range(1, d + 1):
        kazu, bonus = map(int, input().split())
        score_p = []
        for i2 in range(kazu):
            score_p.append(i1 * 100 * i2)
        score_p.append(i1 * 100 * kazu + bonus)
        score_set.append(score_p)
        score_set_qnum.append(range(kazu + 1))
    score_set_pat = tuple(product(*score_set))
    score_set_qnum_pat = tuple(product(*score_set_qnum))

    inf = float('inf')
    r = inf
    for sset, ssetq in zip(score_set_pat, score_set_qnum_pat):
        sset_sum = sum(sset)
        if sset_sum >= g:
            r = min(r, sum(ssetq))
    print(r)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
def main():
    d, g = map(int, input().split())
    score_set = []
    score_pat = []
    for i1 in range(1, d + 1):
        kazu, bonus = map(int, input().split())
        score = [i1, kazu, bonus]
        score_set.append(score)
        score_pat.append(range(kazu + 1))
    score_get_pat = tuple(product(*score_pat))
    inf = float('inf')
    r = inf
    for scpe in score_get_pat:
        score_e  = 0
        for j1 in range(d):
            score_e += scpe[j1] * score_set[j1][0] * 100
            if scpe[j1] == score_set[j1][1]:
                score_e += score_set[j1][2]
        if score_e >= g:
            r = min(r, sum(scpe))
    print(r)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys, math
from itertools import permutations
sys.setrecursionlimit(300000)


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    perms = list(permutations(list(range(D))))
    ret = float('inf')
    for A in perms:
        g = G
        cnt = 0
        for i in A:
            base = (i + 1) * 100 * p[i]
            total = base + c[i]
            if total < g:
                g -= total
                cnt += p[i]
            elif base >= g:
                cnt += math.ceil(g / ((i + 1) * 100))
                break
            else:
                cnt += p[i]
                break
        ret = min(ret, cnt)
    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())
P = [0]*d
C = [0]*d
for i in range(d):
  P[i],C[i] = map(int,input().split())
  
x = 10**4
INF = 10**10
dp = [[INF]*(g//100+x) for _ in range(d+1)]
dp[0][0]=0

for i in range(1,d+1):
  for j in range(P[i-1]):
    
    q = j+1
    score = q*i    
    
    if q == P[i-1]:
      score += C[i-1]//100
    #print(i,j,P[i-1],score)
    for k in range(g//100+x):
      dp[i][k] = min(dp[i][k],dp[i-1][k])
      if k - score >= 0:
        dp[i][k] = min(dp[i][k],dp[i-1][k-score]+q)      
        
print(min(dp[-1][g//100:]))

Submission status: Time Limit Exceeded

Solution code:
D,G=map(int,input().split(" "))
ps=[]
for i in range(D):
    ps.append(list(map(int,input().split(" "))))
dp=[]
    
def minq(p,g):
    if g <= 0:
        return 0
    for i in range(len(dp)):
        if p==dp[i][0]:
            return dp[i][1]
    res=10**8
    for i in range(D):
        if p[i][0]==1:
            p[i][0]-=1
            res=min(1+minq(p,g-100*(i+1)-p[i][1]),res)
            dp.append([[p],[res]])
            p[i][0]+=1
        if p[i][0] >= 2:
            p[i][0]-=1
            res=min(1+minq(p,g-100*(i+1)),res)
            p[i][0]+=1
    return res

print(minq(ps,G))

Submission status: Time Limit Exceeded

Solution code:
D,G=map(int,input().split(" "))
ps=[]
for i in range(D):
    ps.append(list(map(int,input().split(" "))))
    
def minq(p,g):
    if g <= 0:
        return 0
    res=10**8
    for i in range(D):
        if p[i][0]==1:
            p[i][0]-=1
            res=min(1+minq(p,g-100*(i+1)-p[i][1]),res)
            p[i][0]+=1
        if p[i][0] >= 2:
            p[i][0]-=1
            res=min(1+minq(p,g-100*(i+1)),res)
            p[i][0]+=1
    return res

print(minq(ps,G))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations


def get_result(case, bonus):
    result = sum(case)
    for key, value in bonus.items():
        if case.count(value["target"]) == value["count"]:
            result += key
    return result


# input
D, G = map(int, input().split())
bonus = {}
points = []
all_qc = 0
for n in range(1, D + 1):
    p, c = map(int, input().split())
    bonus[c] = {
        "target": 100 * n,
        "count": p
    }
    points += [100 * n] * p
    all_qc += p


for n in range(1, all_qc + 1):
    for c in list(combinations(points, n)):
        if get_result(c, bonus) >= G:
            print(n)
            exit(0)

Submission status: Time Limit Exceeded

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

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

from itertools import permutations
from math import ceil
ans=float("INF")
for t in permutations(range(1,D+1)):
    #print(t)
    t=list(t)
    now=G
    sub=0
    for x in t:
        p,c=L[x-1]
        if now/(x*100)<=p:
            sub+=ceil(now/(x*100))
            break
        elif x*p*100+c>=now:
            sub+=p
            break
        else:
            now-=x*p*100+c
            sub+=p

    #print(t, sub)
    ans=min(ans, sub)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from itertools import permutations

D, G = map(int, input().split(' '))
questions = [tuple(map(int, input().split(' '))) for _ in range(D)]

min_answer = 1000

for question_ids in permutations(range(D)):
    score = G
    answer = 0
    for question_id in question_ids:
        n, bonus = questions[question_id]
        point = 100 * (question_id + 1)
        n_ans = min(n, math.ceil(score / point))
        answer += n_ans
        score -= n_ans * point
        if n_ans == n:
            score -= bonus
        if score <= 0:
            min_answer = min(min_answer, answer)
            break

print(min_answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        while score < g:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                for _ in range(pc[i][0]):
                    if score >= g:
                        break
                    score += 100 * (i + 1)
                    c += 1

        ans = min(ans, c)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def main():
    d, g = MI()
    data = np.array([LI() for _ in range(d)], np.int64)
    p = data[:, 0]
    c = data[:, 1]

    problems = np.zeros(2 ** d, np.int64)
    points = np.zeros(2 ** d, np.int64)
    for i in range(d):
        problems[1 << i : 1 << (i + 1)] = problems[: 1 << i] + p[i]
        points[1 << i : 1 << (i + 1)] = points[: 1 << i] + c[i] + 100 * (i + 1) * p[i]

    for i in range(2 ** d):
        point = points[i]
        problem = problems[i]
        while point < g:
            for j in reversed(range(d)):
                if (i >> j) & 1:
                    continue
                for _ in range(p[j]):
                    if point >= g:
                        break
                    point += 100 * (j + 1)
                    problem += 1
        problems[i] = problem

    print(problems.min())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    d, g = MI()
    data = np.array([LI() for _ in range(d)], np.int64)
    p = data[:, 0]
    c = data[:, 1]

    problems = np.zeros(2 ** d, np.int64)
    points = np.zeros(2 ** d, np.int64)
    for i in range(d):
        problems[1 << i : 1 << (i + 1)] = problems[: 1 << i] + p[i]
        points[1 << i : 1 << (i + 1)] = points[: 1 << i] + c[i] + 100 * (i + 1) * p[i]

    for i in range(2 ** d):
        while points[i] < g:
            for j in reversed(range(d)):
                if (i >> j) & 1:
                    continue
                for _ in range(p[j]):
                    if points[i] >= g:
                        break
                    points[i] += 100 * (j + 1)
                    problems[i] += 1

    print(problems.min())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
ac=[0]*d
for i in range(d):
    ac[i]=pc[i][0]*(i+1)*100+pc[i][1]

def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)

mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    sum2 = 0
    for j in range(d):
        if i[j]==1:
            sum+=ac[j]
            cost+=pc[j][0]
            sum2+=ac[j]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
            sum2+=ac[j]
    if sum2<g:
        continue
    stock.sort()
    while sum<g and stock:
        sum+=stock.pop()
        cost+=1
    if sum>=g:
        mi=min(mi,cost)

print(mi)

Submission status: Time Limit Exceeded

Solution code:
d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
ac=[0]*d
for i in range(d):
    ac[i]=pc[i][0]*(i+1)*100+pc[i][1]

def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)

mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    for j in range(d):
        if i[j]==1:
            sum+=ac[j]
            cost+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
    stock.sort()
    while sum<g and stock:
        sum+=stock.pop()
        cost+=1
    if sum>=g:
        mi=min(mi,cost)

print(mi)

Submission status: Time Limit Exceeded

Solution code:
d , g = map(int, input().split())
pc = [list(map(int, input().split()))for i in range(d)]
x=[]
y=[0]*d
def dfs(n,m,y,now):
    if now==n:
        z=y.copy()
        x.append(z)
        return
    for i in range(m):
        y[now]=i
        dfs(n,m,y,now+1)
dfs(d,3,y,0)

mi = 1000
for i in x:
    sum = 0
    cost = 0
    stock = []
    for j in range(d):
        if i[j]==1:
            sum+=pc[j][0]*(j+1)*100+pc[j][1]
            cost+=pc[j][0]
        if i[j]==2:
            stock+=[(j+1)*100]*pc[j][0]
    stock.sort()
    while sum<g and stock:
        sum+=stock.pop()
        cost+=1
    if sum>=g:
        mi=min(mi,cost)

print(mi)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from pprint import pprint
import sys 


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

plist=[]
clist=[]

bonus_masterlist=[]

for _ in range(d):
    p_temp,c_temp = map(int,input().split())
    plist.append(p_temp)
    clist.append(c_temp)


bonus_masterlist = list(itertools.product(range(2), repeat=d))
#bit全探索をやらなくても、itertoolsを使えば一瞬でできちゃう。(タプルのリスト)
#for i in range(2**d):
#    bonus_templist = [0] * d
#    for j in range(d):
#        if i >> j & 1:
#            bonus_templist[d-1-j] = 1
#    bonus_masterlist.append(bonus_templist)

#point_list = [100,200,300, ... ,d*100]
#max_list: plist = [p[0],p[1],p[2], ... ,p[d]]
#bonuspoint_list: clist = [c[0],c[1],c[2], ... ,c[d]]

count_list = [0] * d

mincount = 100 * 10

"""
def dfs(i):
    global mincount
    if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
        if sum(count_list) < mincount:
            mincount = sum(count_list)
    elif plist[i] == count_list[i]:
        bonus_list[i] = 1
        dfs(i-1)
    elif plist[i] > count_list[i]:
        count_list[i] += 1
        dfs(i)
    return
"""

for bonus_tuple in bonus_masterlist:
    bonus_list = list(bonus_tuple)
    count_list = [x * y for (x, y) in zip(bonus_list, plist)]
    i = d-1
    while True:
        if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
            if sum(count_list) < mincount:
                mincount = sum(count_list)
            break
        elif plist[i] == count_list[i]:
            bonus_list[i] = 1
            i -= 1
            continue
        elif plist[i] > count_list[i]:
            count_list[i] += 1
            continue


print(mincount)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from pprint import pprint
import sys 
sys.setrecursionlimit(10*100*1024)
#基本的に10*100*len(bonus_masterlist)回ループを回せばよい
#len(bonus_masterlist)は最大で2**10=1024

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

plist=[]
clist=[]

bonus_masterlist=[]

for _ in range(d):
    p_temp,c_temp = map(int,input().split())
    plist.append(p_temp)
    clist.append(c_temp)


bonus_masterlist = list(itertools.product(range(2), repeat=d))
#bit全探索をやらなくても、itertoolsを使えば一瞬でできちゃう。(タプルのリスト)
#for i in range(2**d):
#    bonus_templist = [0] * d
#    for j in range(d):
#        if i >> j & 1:
#            bonus_templist[d-1-j] = 1
#    bonus_masterlist.append(bonus_templist)

#point_list = [100,200,300, ... ,d*100]
#max_list: plist = [p[0],p[1],p[2], ... ,p[d]]
#bonuspoint_list: clist = [c[0],c[1],c[2], ... ,c[d]]

count_list = [0] * d

mincount = 100 * 10

def dfs(target):
    global mincount
    if sum([count_list[i] * 100*(i+1) for i in range(d)]) + sum([bonus_list[j] * clist[j] for j in range(d)]) >= g:
        if sum(count_list) < mincount:
            mincount = sum(count_list)
        return
    elif plist[target] == count_list[target]:
        bonus_list[target] = 1
        dfs(target-1)
    elif plist[target] > count_list[target]:
        count_list[target] += 1
        dfs(target)

for bonus_tuple in bonus_masterlist:
    bonus_list = list(bonus_tuple)
    count_list = [x * y for (x, y) in zip(bonus_list, plist)]
    dfs(d-1)

print(mincount)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, g = map(int, input().split())
L = []
for i in range(n):
    t = list(map(int, input().split()))
    # 得点の情報を追加
    t.append((i+1)*100)
    L.append(t)

ans = 100 * n
for v in itertools.permutations(L):
    # print(v)
    score = 0
    count = 0
    k = 0
    p = v[k][0]
    while score < g:
        score += v[k][2]
        p -= 1
        count += 1
        if p == 0:
            score += v[k][1]
            k += 1
            if k < n:
                p = v[k][0]
        # print(v,count,score,k,p)
    ans = min(ans, count)
print(ans)

# ミス
# P = []
# G = []
# for i in range(n):
#     s, t = map(int, input().split())
#     P.insert(0, s)
#     G.insert(0, t//100)
# score = 0
# k = 0
# count = 0
# while score < g:
#     count += 1
#     if 1 in P:
#         j = P.index(1)
#         score += n-j + G[j]
#         P[j] = 0
#         if j == k:
#             k += 1
#     else:
#         score += n-k
#         P[k] -= 1
#     print(P,G,score,count,k)
# print(count)

Submission status: Time Limit Exceeded

Solution code:
d, g = map(int, input().split())

p = []
c = []

for i in range(d):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)

minp = sum(p)

def min_plobrem(p,c):
    res = []
    if len(p) == 1:
        for i in range(p[0]+1):
            point = 100 * i
            if i == p[0]:
                point += c[0]
            res.append([point,i])
    else:
        for lelse in min_plobrem(p[:-1],c[:-1]):
            for i in range(p[-1]+1):
                point = 100 * len(p) * i
                if i == p[-1]:
                    point += c[-1]
                res.append([lelse[0]+point, lelse[1]+i])
    return(res)

results = min_plobrem(p,c)
for result in results:
    if result[0] >= g:
        minp = min(minp, result[1])

print(minp)

Submission status: Time Limit Exceeded

Solution code:
D, G = list(map(int, input().split(' ')))
p_list = list()
c_list = list()
for _ in range(D):
    p, c = list(map(int, input().split(' ')))
    p_list.append(p)
    c_list.append(c)
num_prob_list = [0] * D
min_prob_num_sum = sum(p_list)


def dfs(prob_index=-1, prob_num=0, current_prob_num_sum=0, current_score=0):
    """
    Returns whether score >= G with local minimum of problems.
    """
    global min_prob_num_sum
    if prob_index >= 0:
        current_prob_num_sum += prob_num
        if current_prob_num_sum >= min_prob_num_sum:
            return False
        num_prob_list[prob_index] = prob_num
        current_score += 100 * (prob_index + 1) * prob_num
        if prob_num == p_list[prob_index]:
            current_score += c_list[prob_index]
        if current_score >= G:
            min_prob_num_sum = current_prob_num_sum
            # print(num_prob_list[:(prob_index + 1)])
            # print(current_score)
            return True
    next_prob_index = prob_index + 1
    if next_prob_index > D - 1:
        return False
    for next_prob_num in range(p_list[next_prob_index] + 1):
        if dfs(next_prob_index, next_prob_num, current_prob_num_sum, current_score):
            break


dfs()
print(min_prob_num_sum)

Submission status: Time Limit Exceeded

Solution code:
D, G = list(map(int, input().split(' ')))
p_list = list()
c_list = list()
for _ in range(D):
    p, c = list(map(int, input().split(' ')))
    p_list.append(p)
    c_list.append(c)
num_prob_list = [0] * D
min_prob_num_sum = sum(p_list)


def dfs(prob_index=-1, prob_num=0, current_score=0):
    """
    Returns whether score >= G.
    """
    global min_prob_num_sum
    if prob_index >= 0:
        num_prob_list[prob_index] = prob_num
        current_score += 100 * (prob_index + 1) * prob_num
        if prob_num == p_list[prob_index]:
            current_score += c_list[prob_index]
        if current_score >= G:
            prob_num_sum = sum(num_prob_list[:(prob_index + 1)])
            if min_prob_num_sum > prob_num_sum:
                min_prob_num_sum = prob_num_sum
                # print(num_prob_list[:(prob_index + 1)])
                # print(current_score)
            return True
    next_prob_index = prob_index + 1
    if next_prob_index > D - 1:
        return False
    for next_prob_num in range(p_list[next_prob_index] + 1):
        if dfs(next_prob_index, next_prob_num, current_score):
            break


dfs()
print(min_prob_num_sum)