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:
import copy
import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)
 
m = 10**9
def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif point+100*(now+1)*P[now] >= g:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: 
            m = n
    else:
        done.append(now)
        for i in range(d):
            if not i in done:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, copy.copy(done))
 
for i in range(d):
    done = []
    score(0,0,i,done)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = 10**9

def flag(point,P,now):
    if point+100*(now+1)*P >= g:
        return 1
    else:
        return 0

def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif flag(point,P[now],now):
            for i in range(1,P[now]+1):
                point += 100*(now+1)
                n += 1
                if point >= g:
                    if m > n:
                        m = n
                        break
    else:
        donecp = copy.copy(done)
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = 10**9
def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif point+100*(now+1)*P[now] >= g:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: 
            m = n
    else:
        done.append(now)
        for i in range(d):
            if not i in done:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, copy.copy(done))

for i in range(d):
    done = []
    score(0,0,i,done)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = 10**9

def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif point+100*(now+1)*P[now] >= g:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: 
            m = n
    else:
        donecp = copy.copy(done)
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import time
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

# start = time.time()

m = 10**9

def flag(point,P,now):
    if point+100*(now+1)*P >= g:
        return 1
    else:
        return 0

def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif flag(point,P[now],now):
            for i in range(1,P[now]+1):
                point += 100*(now+1)
                n += 1
                if point >= g:
                    if m > n:
                        m = n
                        break
    else:
        donecp = copy.copy(done)
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

# elapsed_time = time.time() - start

print(m)

Submission status: Time Limit Exceeded

Solution code:
import time
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

# start = time.time()

m = 10**9

def flag(point,P,now):
    if point+100*(now+1)*P >= g:
        return 1
    else:
        return 0

def score(point = 0, n = 0, now=0, done=[]):
    global m
    if point >= g:
        if m > n: m = n
    elif flag(point,P[now],now):
            for i in range(1,P[now]+1):
                point += 100*(now+1)
                n += 1
                if point >= g:
                    if m > n:
                        m = n
                        break
    else:
        donecp = copy.deepcopy(done)
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

# elapsed_time = time.time() - start

print(m)

Submission status: Time Limit Exceeded

Solution code:
import time
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

# start = time.time()

m = 10**9
maxp = d-1

def flag(point,P,now):
    if point+100*(now+1)*P >= g:
        return 1
    else:
        return 0

def score(point = 0, n = 0, now=0, done=[]):
    global m
    donecp = copy.deepcopy(done)
    if point >= g:
        if m > n: m = n
    else:
        if flag(point,P[now],now):
            for i in range(1,P[now]+1):
                point += 100*(now+1)
                n += 1
                if point >= g:
                    if m > n:
                        m = n
                        break
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

# elapsed_time = time.time() - start

print(m)

Submission status: Time Limit Exceeded

Solution code:
import time
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

start = time.time()

m = 10**9
def score(point = 0, n = 0, now=0, done=[]):
    global m
    donecp = copy.deepcopy(done)
    if point >= g:
        if m > n: m = n
    else:
        pointcp = point
        ncp = n
        maxp = d - 1
        while (maxp >= 0):
            if not maxp in donecp:
                break
            else:
                maxp -= 1 
        for i in range(1,P[maxp]+1):
            pointcp += 100*(maxp+1)
            ncp += 1
            if pointcp >= g:
                if m > ncp:
                    m = ncp
                break
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

elapsed_time = time.time() - start

print(m)

Submission status: Time Limit Exceeded

Solution code:
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = 10**9
def score(point = 0, n = 0, now=0, done=[]):
    global m
    donecp = copy.deepcopy(done)
    if point >= g:
        if m > n: m = n
    else:
        pointcp = point
        ncp = n
        for i in range(1,P[now]+1):
            pointcp += 100*(now+1)
            ncp += 1
            if pointcp >= g:
                if m > ncp:
                    m = ncp
                break
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

print(m)

Submission status: Time Limit Exceeded

Solution code:
import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = []
def score(point = 0, n = 0, now=0, done=[]):
    donecp = copy.deepcopy(done)
    if point >= g:
        m.append(n)
    else:
        pointcp = point
        ncp = n
        for i in range(1,P[now]+1):
            pointcp += 100*(now+1)
            ncp += 1
            if pointcp >= g:
                m.append(ncp)
                break
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

print(min(m))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G:# or q_num > min_q:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G or q_num > min_q:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + spc_list[q_idx][0] * spc_list[q_idx][1] + spc_list[q_idx][2] < G:
                score += spc_list[q_idx][0] * spc_list[q_idx][1] + spc_list[q_idx][2]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G or q_num > min_q:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + spc_list[q_idx][0] * spc_list[q_idx][1] + spc_list[q_idx][2] < G:
                score += spc_list[q_idx][0] * spc_list[q_idx][1] + spc_list[q_idx][2]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(4100000)
from functools import lru_cache
INF = 1 << 60

#ここから書き始める
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())
ans = INF

def dfs(cnt, total, a):
    global ans
    global p, c, g
    # print(cnt, total, a)
    if total >= g:
        ans = min(ans, cnt)
        return
    if cnt >= ans:
        return
    for i in range(d):
        if a[i] < p[i] - 1:
            dfs(cnt + 1, total + (i + 1) * 100, a[:i] + [a[i] + 1] + a[i + 1:])
        elif a[i] == p[i] - 1:
            dfs(cnt + 1, total + (i + 1) * 100 + c[i], a[:i] + [a[i] + 1] + a[i + 1:])
        else:
            return

dfs(0, 0, [0] * d)
print(ans)

Submission status: Time Limit Exceeded

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

lst = [list(map(int, input().split())) for i in range(d)]
#print(lst)

new_lst = [[] for i in range(len(lst))]

for i, j in enumerate(lst):
    #print(i, j)
    for k in range(j[0] + 1):
        new_lst[i].append([k, (k * 100 * (i + 1))])
        if k == j[0]:
            new_lst[i][k][1] += j[1]
        
#print(new_lst)
min_ac = 1000

for i in itertools.product(*new_lst):
    ac = 0
    points = 0
    #print(i)
    for j in range(len(lst)):
        ac += i[j][0]
        points += i[j][1]
    if points >= g:
        if ac <= min_ac:
            min_ac = ac

print(min_ac)

Submission status: Time Limit Exceeded

Solution code:
D,G = map(int,input().split())
pc = [list(map(int,input().split())) for _ in range(D)]
from itertools import permutations
#%%
import math
INF = 1<<30
ans = INF
A = [i for i in range(D)]

permu = permutations(A)

for pp in permu:
    points = 0
    count = 0
    for i in pp:
        if points>=G:
            break
        if points+(i+1)*100*pc[i][0]>=G:
            count += math.ceil((G-points)/(100*(i+1)))
            break
        else:
            count += pc[i][0]
            points += (i+1)*100*pc[i][0]+pc[i][1]
        
    ans = min(ans,count)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
d,g=[int(c) for c in input().split(" ")]

p=[0]*d
c=[0]*d

for i in range(d):
    pp,cc=[int(c) for c in input().split(" ")]
    p[i]=pp
    c[i]=cc

ans=1001

def calc(g,n):
    if g<=0:
        return 0
    elif n==d:
        return 100001
    cnt=100001
    for i in range(p[n]):
        cnt=min(cnt,i+calc(g-100*i*(n+1),n+1))
    cnt=min(cnt,p[n]+calc(g-p[n]*(n+1)*100-c[n],n+1))

    return cnt

print(calc(g,0))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
D,G=map(int,input().split(" "))
Problem=[]
Comp={}
n=0
for i in range(D):
  p,c=map(int,input().split(" "))
  n+=p
  [Problem.append(100*(i+1)) for _ in range(p)]
  Comp[i+1]=[p,c]
Min=1000000000
for i in range(2**(n)):
  score=0
  Clear=[]
  for j in range(n):
    if ((i>>j)&1):
      score+=Problem[j]
      Clear.append("○")
    else:
      Clear.append("×")
  No=1
  Count=0
  mark_count=0
  for bin in Clear:
    if bin=="○":
      mark_count+=1
    Count+=1
    if Count==Comp[No][0]:
      if mark_count==Comp[No][0]:
      	score+=Comp[No][1]
      No+=1
      Count=0
      mark_count=0
  Mark_all=Clear.count("○")
  if score>=G:
    Mark_all=Clear.count("○")
    Min=min([Min,Mark_all])
print(Min)

Submission status: Time Limit Exceeded

Solution code:
# 小さいのでメモ化再帰でいけるか？
# （[ここまでの回答数, ここまでの点数]みたいなやつ）
# んーーーーーー？？？？ RE*1、あとTLEになる。。。
# REはどうせ再帰の制限
import sys

sys.setrecursionlimit(10 ** 8)

d, g = map(int, input().split())
memo = {}
points, bonus = [], []
for _ in range(d):
    p, c = map(int, input().split())
    points.append(p)
    bonus.append(c)


def f(c, p):
    # if (c, p) in memo:
    #     return memo[(c, p)]
    if p >= g:
        return c
    ret = 10 ** 10
    for i in range(d):
        if points[i] == 1:
            points[i] = 0
            ret = min(ret, f(c + 1, p + (i + 1) * 100 + bonus[i]))
            points[i] = 1
        elif points[i] > 1:
            points[i] -= 1
            ret = min(ret, f(c + 1, p + (i + 1) * 100))
            points[i] += 1
        elif points[i] == 0:
            continue
        else:
            print(3 / 0)
    memo[(c, p)] = ret
    return ret


print(f(0, 0))

Submission status: Time Limit Exceeded

Solution code:
# 小さいのでメモ化再帰でいけるか？
# （[ここまでの回答数, ここまでの点数]みたいなやつ）
# んーーーーーー？？？？ RE*1、あとTLEになる。。。
# REはどうせ再帰の制限
import sys

sys.setrecursionlimit(10 ** 8)

d, g = map(int, input().split())
memo = {}
points, bonus = [], []
for _ in range(d):
    p, c = map(int, input().split())
    points.append(p)
    bonus.append(c)


def f(c, p):
    if (c, p) in memo:
        return memo[(c, p)]
    if p >= g:
        return c
    ret = 10 ** 10
    for i in range(d):
        if points[i] == 1:
            points[i] = 0
            ret = min(ret, f(c + 1, p + (i + 1) * 100 + bonus[i]))
            points[i] = 1
        elif points[i] > 1:
            points[i] -= 1
            ret = min(ret, f(c + 1, p + (i + 1) * 100))
            points[i] += 1
        elif points[i] == 0:
            continue
        else:
          print(3/0)
    memo[(c, p)] = ret
    return ret


print(f(0, 0))

Submission status: Time Limit Exceeded

Solution code:
# 小さいのでメモ化再帰でいけるか？
# （[ここまでの回答数, ここまでの点数]みたいなやつ）
# んーーーーーー？？？？ RE*1、あとTLEになる。。。
# REはどうせ再帰の制限
import sys

sys.setrecursionlimit(10 ** 8)

d, g = map(int, input().split())
memo = {}
points, bonus = [], []
for _ in range(d):
    p, c = map(int, input().split())
    points.append(p)
    bonus.append(c)


def f(c, p):
    if (c, p) in memo:
        return memo[(c, p)]
    if p >= g:
        return c
    ret = 10 ** 10
    for i in range(d):
        if points[i] == 1:
            points[i] = 0
            ret = min(ret, f(c + 1, p + (i + 1) * 100 + bonus[i]))
            points[i] = 1
        elif points[i] > 1:
            points[i] -= 1
            ret = min(ret, f(c + 1, p + (i + 1) * 100))
            points[i] += 1
        else:
            continue
    memo[(c, p)] = ret
    return ret


print(f(0, 0))

Submission status: Time Limit Exceeded

Solution code:
D,G = map(int, input().split())
L=[[0,0] for i in range(D)]

for i in range(D):
    L[i][0],L[i][1]=map(int, input().split())

MAP=[0]*(D+1)
i=0
a=10**10
while(MAP[-1]!=1):
    for j in range(D):
        if MAP[j] > L[j][0]:
            MAP[j] -= (L[j][0]+1)
            MAP[j+1]+=1 
    if(sum(MAP)<a):
        s=0
        for j in range(D):   
            s+=MAP[j]*(j+1)*100
            if(MAP[j] == L[j][0]):
                s+=L[j][1]
        if(s>=G):
            a=sum(MAP)
            #print(a,MAP)
    MAP[0]+=1

print(a)

Submission status: Time Limit Exceeded

Solution code:
class Problem:
  def __init__(self, score, number, bonus):
    self.score = score
    self.number = number
    self.bonus = bonus
    
  def score_at(self, number):
    if number >= self.number:
      return self.number * self.score + self.bonus
    return number * self.score


D, G = (int(x) for x in input().split())

problems = []

for i in range(1, D + 1):
  n, b = (int(x) for x in input().split())
  problems.append(Problem(i * 100, n, b))

memo = [[0] * 1001 for _ in range(D)]

def solve():
  for number in range(0, 1001):  # 解いた問題数
    for i in range(D):
      # 一行目の初期化
      if i == 0:
        memo[i][number] = problems[i].score_at(number)
      else:
        memo[i][number] = max(
          memo[i - 1][number - n] +problems[i].score_at(n)
          for n in range(0, number + 1)
        )
    if memo[D - 1][number] >= G:
      return number

print(solve())

Submission status: Time Limit Exceeded

Solution code:
D, G = map(int, input().split())
G = G // 100
sumn = 0
ns = [0] * (D + 1)
cs = [0] * (D + 1)
cache = [{} for _ in range(D + 1)]
for i in range(1, D + 1):
    n, c = map(int, input().split())
    ns[i] = n
    cs[i] = c // 100
    sumn += n

minn = [0] * (D + 1)
for i in range(1, D + 1):
    minn[i] = min(ns[1:i+1])

def f(i, rn):
    if i == 1:
        if ns[1] < rn:
            return -1
        p = rn
        if ns[1] == rn:
            p += cs[1]
        return p
    if rn < minn[i]:
        p = 0
        for j in range(i, 0, -1):
            n = min((ns[j], rn))
            p += j * n
            if n == rn:
                break
            rn -= n
        return p
    maxp = 0
    for n in range(min((ns[i], rn)) + 1):
        p = i * n
        if n == ns[i]:
            p += cs[i]
        nn = rn - n
        cch = cache[i - 1]
        np = cch.get(nn)
        if not np:
            np = f(i - 1, nn)
            cch[nn] = np
        if np >= 0:
            p += np
            if maxp < p:
                maxp = p
    return maxp

mn = 1
mx = sumn
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if G <= f(D, x):
        mx = x
    else:
        mn = x + 1
print(mn)

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())


# リスト生成
# [[0, 1, 2, 3], [0, 1, 2, 3, 4, 5]]
lis = [[] for i in range(len(p))]
# print(lis)
for i in range(len(p)):
    for j in range(p[i]+1):
        lis[i].append(j)
# print(lis)

# -------------------------------------------------------------------------
# https://youkoso-guest.hatenadiary.org/entry/20081212/1229089595
# 直積作成
from functools import reduce

# 直積を求める関数
def product(lists):
    return reduce(
        lambda prod, list: [x + [y] for x in prod for y in list],
        lists, [[]])
# -------------------------------------------------------------------------

chokuseki = product(lis)
# print(chokuseki)

def keisan(lis):
#     global p, c, D, G
    goukei = 0
    for i in range(D):
        goukei += (i+1) * 100 * lis[i]
        if lis[i] == p[i]:
            goukei += c[i]
#         print(goukei)
    
    if goukei >= G:
        return(sum(lis))

scores = []
for x in chokuseki:
    if keisan(x) != None:
        scores.append(keisan(x))

print(min(scores))

Submission status: Time Limit Exceeded

Solution code:
D, G = map(int, input().split())
ncs = [list(map(int, input().split())) for _ in range(D)]
ns = [x[0] for x in ncs]
cs = [x[1] for x in ncs]

def f(i, rn, rp):
    if i == 0:
        if ns[0] < rn:
            return False
        rp -= 100 * rn
        if ns[0] == rn:
            rp -= cs[0]
        return rp <= 0
    if rn < min(ns[:i+1]):
        for j in range(i, -1, -1):
            n = min((ns[j], rn))
            rp -= (j + 1) * 100 * n
            rn -= n
            if rn == 0:
                break
        return rp <= 0
    for n in range(min((ns[i], rn)) + 1):
        p = (i + 1) * 100 * n
        if n == ns[i]:
            p += cs[i]
        if n == rn:
            return p >= rp
        if p >= rp:
            return True
        if f(i - 1, rn - n, rp - p):
            return True
    return False

mn = 1
mx = sum(ns)
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if f(D - 1, x, G):
        mx = x
    else:
        mn = x + 1
print(mn)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
D, G = map(int, input().split())       
npcs = []
for i in range(D):
    n, c = map(int, input().split())   
    p = (i + 1) * 100
    npcs.append((n, p, c))
npcs.sort(key=lambda x: x[0])
lmaxn, lp, lc = npcs[-1]
lmaxp = lmaxn * lp + lc
lmaxp2 = (lmaxn - 1) * lp
result = sum(map(lambda x: x[0], npcs))

nps = [
[(x, p * x + (c if x == n else 0)) for x in range(n + 1)]
for n, p, c in npcs[:-1]
]
for np in product(*nps):
    sumn = sum(map(lambda x: x[0], np))
    if sumn >= result:
        continue
    sump = sum(map(lambda x: x[1], np))
    if sump >= G:
        result = sumn
    else:
        ps = G - sump
        if ps <= lmaxp:
            if ps > lmaxp2:
                sumn += lmaxn
            else:
                sumn += ps // lp
                if ps % lp != 0:
                    sumn += 1
            if sumn < result:
                result = sumn
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
D, G = map(int, input().split())
npcs = []
for i in range(D):
    n, c = map(int, input().split())
    p = (i + 1) * 100
    npcs.append((n, p, c))
npcs.sort(key=lambda x: x[0])
lmaxn, lp, lc = npcs[-1]
lmaxp = lmaxn * lp + lc
lmaxp2 = (lmaxn - 1) * lp
result = sum(map(lambda x: x[0], npcs))

nps = [
[(x, p * x + (c if x == n else 0)) for x in range(n + 1)]
for n, p, c in npcs[:-1]
]
for np in product(*nps):
    sumn = sum(map(lambda x: x[0], np))
    if sumn >= result:
        continue
    sump = sum(map(lambda x: x[1], np))
    if sump >= G:
        result = sumn
    else:
        ps = G - sump
        if ps <= lmaxp:
            if ps > lmaxp2:
                sumn += lmaxn
            else:
                sumn += ps // lp
                if ps % lp != 0:
                    sumn += 1
            if sumn < result:
                result = sumn
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
D, G = map(int, input().split())
npcs = []
for i in range(D):
    n, c = map(int, input().split())
    p = (i + 1) * 100
    npcs.append((n, p, c))
npcs.sort(key=lambda x: x[0])
result = sum(map(lambda x: x[0], npcs))
for ns in product(*[range(n + 1) for n, p, c in npcs[:-1]]):
    sump = 0
    sumn = 0
    for i, n in enumerate(ns):
        maxn, p, c = npcs[i]
        sump += n * p
        if n == maxn:
            sump += c
        sumn += n
    if sump >= G:
        if sumn < result:
            result = sumn
    else:
        s = G - sump
        lmaxn, lp, lc = npcs[-1]
        if s <= lmaxn * lp + lc:
            if s > (lmaxn - 1) * lp:
                sumn += lmaxn
            else:
                sumn += s // lp
                if s % lp != 0:
                    sumn += 1
            if sumn < result:
                result = sumn
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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())
ANS = float("inf")
for perm in permutations(range(D)):
    ans = 0
    g = G
    for i in perm:
        if g <= 0:
            break
        for _ in range(P[i]):
            if g <= 0:
                break
            ans += 1
            g -= 100 * (i + 1)
        else:
            g -= C[i]
    ANS = min(ANS, ans)
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
D, G = map(int, input().split())
pc = [tuple(map(int, input().split())) for _ in range(D)]
p = [x[0] for x in pc]
c = [x[1] for x in pc]
result = sum(p)
for nums in product(*map(range, [pp + 1 for pp in p])):
    n = sum(nums)
    if n >= result:
        continue
    point = 0
    for i, num in enumerate(nums):
        point += (i + 1) * 100 * num
        if num == p[i]:
            point += c[i]
    if point >= G:
        result = n
print(result)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
D, G = map(int, input().split())
p = []
c = []
for _ in range(D):
    pc = list(map(int, input().split()))
    p.append(pc[0])
    c.append(pc[1])

def acceptable_point(pnums):
    point = 0
    for i, pnum in enumerate(pnums):
        point += (i + 1) * 100 * pnum
        if pnum == p[i]:
            point += c[i]
    return point >= G

result = min(
    map(sum,
        filter(acceptable_point,
            product(*map(range, [pp + 1 for pp in p]))
        )
    )
)
print(result)