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: Accepted

Solution code:
from itertools import permutations, product
from math import ceil, floor

D, G = [int(elem) for elem in input().split(' ')]
point_info_list = [[int(elem) for elem in input().split()] for _ in range(D)]
assert len(point_info_list) == D
assert len(point_info_list[0]) == 2

# time complexity: O(D!)
""" min_num = float('inf')
for perm in permutations(range(D)):
    current_point = 0
    current_num = 0
    for point in perm:
        if (G - current_point) - (point + 1) * 100 * point_info_list[point][0] <= 0:
            current_num += ceil((G - current_point) / ((point + 1) * 100))
            break
        elif (G - current_point) - (point + 1) * 100 * point_info_list[point][0] - point_info_list[point][1] <= 0:
            current_num += point_info_list[point][0]
            break
        else:
            current_point += (point + 1) * 100 * point_info_list[point][0] + point_info_list[point][1]
            current_num += point_info_list[point][0]
    min_num = min(current_num, min_num)

print(min_num)
 """

# time complexity: O(D2^D)
min_num = float('inf')
for mask in product([False, True], repeat=D):
    chosen_indices = [i for i, chosen in enumerate(mask) if chosen]
    current_point = 0
    current_num_solved = 0
    for chosen_index in chosen_indices:
        point = (chosen_index + 1) * 100
        num_problems = point_info_list[chosen_index][0]
        bonus = point_info_list[chosen_index][1]
        current_point += point * num_problems + bonus
        current_num_solved += num_problems

    if current_point >= G:
        min_num = min(min_num, current_num_solved)
    else:
        chosen_indices = set(chosen_indices)
        max_index = max([i for i in range(D) if i not in chosen_indices])
        point = (max_index + 1) * 100
        num_problems = point_info_list[max_index][0]
        if current_point + point * num_problems < G:
            continue
        else:
            current_num_solved += ceil((G - current_point) / point)
            min_num = min(min_num, current_num_solved)

print(min_num)

Submission status: Accepted

Solution code:
inputs = input().strip().split()
D = int(inputs[0])
G = int(inputs[1])

pi = []
ci = []

for i in range(0, D):
    inputs = input().strip().split()
    pi.append(int(inputs[0]))
    ci.append(int(inputs[1]))

bitArray = []
for i in range(0, pow(2, D)):
    bitArray.append(format(i, 'b').zfill(D))

ans = 1000000
for bit in bitArray:
    num = 0
    score = 0
    for index, value in enumerate(bit):
        if value is "1":
            score += (index + 1) * 100 * pi[index] + ci[index]
            num += pi[index]
        else:
            max_zero_index = index  
    for i in range(0, pi[max_zero_index] - 1):
        if score < G:
            num += 1
            score += (max_zero_index + 1) * 100
    if ans > num and score >= G:
        ans = num

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
pcs = [[i] + list(map(int, input().split())) for i in range(1, D + 1)]
from itertools import product
ans = 10 ** 10
for bonus in product(range(2), repeat=D):
    sum_b = 0
    cnt = 0
    for b, (i, p, c) in zip(bonus, pcs):
        if b:
            sum_b += c + i * 100 * p
            cnt += p

    if sum_b >= G:
        ans = min(ans, cnt)

    else:
        for b, (i, p, c) in reversed(list(zip(bonus, pcs))):
            if b:
                continue

            rem = -(-(G - sum_b) // (i * 100))
            sum_b += min(rem, p) * i * 100
            cnt += min(rem, p)
            if sum_b >= G:
                break

        ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import random
import bisect
import math

option = 0     # 0:PSO 1:CFA 2:CFArank
max_or_min = 0 # 0:minimize 1:maxmize

iter=2

N = 50 #粒子の数
T = 1000 #世代数(ループの回数)
maximum=1
minimum=0

dimension, limit = [int(i) for i in input().split()]

pi = [0 for i in range(dimension)]
ci = [0 for i in range(dimension)]
       
for i in range(dimension):
    pi[i], ci[i] = [int(i) for i in input().split()]

tot = [pi[i] * (i+1) * 100 + ci[i] for i in range(dimension)]
#print(pi)
#print(ci)
#print(tot)


#--------粒　子　群　最　適　化------------------------------

#評価関数
def criterion(x):
    
    z = sum([pi[i] * x[i] for i in range(dimension)])
    z2 = sum([tot[i] * x[i] for i in range(dimension)])
    k = -1
    for i in range(dimension):
      if x[dimension -1 -i] == 0:
        k = dimension -1 -i
        break
    if k != -1:
      for i in range(pi[k]):
        if limit > z2:
          z += 1
          z2 +=  (k+1) * 100
        else:
          break

    if limit > z2:
        z = 10000
    return z

#粒子の位置の更新を行う関数
def update_position(x, v, x_min, x_max):
#    new_x = [x_min[i] if x[i]+ v[i] < x_min[i] else x_max[i] if x[i]+ v[i] > x_max[i] else x[i]+ v[i] for i in range(dimension)]
    new_x = [1 if random.uniform(0, 1)< 1/(1+math.e**(-v[i])) else 0 for i in range(dimension)]
    return new_x

#粒子の速度の更新を行う関数
def update_velocity(x, v, p, g, w, ro_max=1.0, c1=2.00, c2=0.75):
    #パラメーターroはランダムに与える
    phi=c1+c2
    K=2/abs(2-phi-(phi*phi-4*phi)**0.5)
    
    #粒子速度の更新を行う
    if option!=0:
        new_v = [K * ( w * v[i] + c1 * random.uniform(0, ro_max) * (p[i] - x[i]) + c2 * random.uniform(0, ro_max) * (g[i] - x[i]) ) for i in range(dimension)]
    else:
        new_v = [w * v[i] + c1 * random.uniform(0, ro_max) * (p[i] - x[i]) + c2 * random.uniform(0, ro_max) * (g[i] - x[i]) for i in range(dimension)]

    return new_v

def main():
    w = 1.0
    w_best, w_worst = 1.25, 0.25
    x_min = [minimum for i in range(dimension)]
    x_max = [maximum for i in range(dimension)]
    
    #粒子位置, 速度, パーソナルベスト, グローバルベストの初期化を行う
    ps = [[random.randint(x_min[j], x_max[j]) for j in range(dimension)] for i in range(N)]
    vs = [[0.0 for j in range(dimension)] for i in range(N)]

    personal_best_positions = ps[:] 
    personal_best_scores = [criterion(p) for p in ps]

    if max_or_min == 1:
        best_particle = personal_best_scores.index(max(personal_best_scores))
    elif max_or_min == 0:
        best_particle = personal_best_scores.index(min(personal_best_scores))
    global_best_position = personal_best_positions[best_particle][:]

    for t in range(T):
        for n in range(N):
            x = ps[n][:]
            v = vs[n][:]
            p = personal_best_positions[n][:]

            if option>=2:
                best_list = sorted(personal_best_positions)
                mu = bisect.bisect_left( best_list, p ) + 1
                w = w_best - mu * (w_best - w_worst) / (N - 1)


            #粒子の位置の更新を行う
            new_x = update_position(x, v, x_min, x_max)
            ps[n] = new_x[:]

            #粒子の速度の更新を行う
            new_v = update_velocity(new_x, v, p, global_best_position, w)
            vs[n] = new_v[:]

            #評価値を求め, パーソナルベストの更新を行う
            score = criterion(new_x)

            if max_or_min == 1:
                if score > personal_best_scores[n]:
                    personal_best_scores[n] = score
                    personal_best_positions[n] = new_x[:]
            elif max_or_min == 0:
                if score < personal_best_scores[n]:
                    personal_best_scores[n] = score
                    personal_best_positions[n] = new_x[:]

        #グローバルベストの更新を行う
        if max_or_min == 1:
            best_particle = personal_best_scores.index(max(personal_best_scores))
            global_best_position = personal_best_positions[best_particle][:]

        elif max_or_min == 0:
            best_particle = personal_best_scores.index(min(personal_best_scores))
            global_best_position = personal_best_positions[best_particle][:]
                     
        f.write(str(max(personal_best_scores))+"\n")
    #最適解
    if max_or_min == 1:
        return max(personal_best_scores)
    elif max_or_min == 0:
        return min(personal_best_scores)

#--------------------------------------------------------------
with open('test_'+ str(option)+".txt", 'w') as f:
    
  if max_or_min == 1:
    best=-float("inf")
    for i in range(iter):
        best=max(best, main())

  elif max_or_min == 0:
    best=float("inf")
    for i in range(iter):
        best=min(best, main())

print(best)

Submission status: Accepted

Solution code:
import random
import bisect
import math

option = 0     # 0:PSO 1:CFA 2:CFArank
max_or_min = 0 # 0:minimize 1:maxmize

iter=3

N = 50 #粒子の数
T = 1000 #世代数(ループの回数)
maximum=1
minimum=0

dimension, limit = [int(i) for i in input().split()]

pi = [0 for i in range(dimension)]
ci = [0 for i in range(dimension)]
       
for i in range(dimension):
    pi[i], ci[i] = [int(i) for i in input().split()]

tot = [pi[i] * (i+1) * 100 + ci[i] for i in range(dimension)]
#print(pi)
#print(ci)
#print(tot)


#--------粒　子　群　最　適　化------------------------------

#評価関数
def criterion(x):
    
    z = sum([pi[i] * x[i] for i in range(dimension)])
    z2 = sum([tot[i] * x[i] for i in range(dimension)])
    k = -1
    for i in range(dimension):
      if x[dimension -1 -i] == 0:
        k = dimension -1 -i
        break
    if k != -1:
      for i in range(pi[k]):
        if limit > z2:
          z += 1
          z2 +=  (k+1) * 100
        else:
          break

    if limit > z2:
        z = 10000
    return z

#粒子の位置の更新を行う関数
def update_position(x, v, x_min, x_max):
#    new_x = [x_min[i] if x[i]+ v[i] < x_min[i] else x_max[i] if x[i]+ v[i] > x_max[i] else x[i]+ v[i] for i in range(dimension)]
    new_x = [1 if random.uniform(0, 1)< 1/(1+math.e**(-v[i])) else 0 for i in range(dimension)]
    return new_x

#粒子の速度の更新を行う関数
def update_velocity(x, v, p, g, w, ro_max=1.0, c1=2.00, c2=0.75):
    #パラメーターroはランダムに与える
    phi=c1+c2
    K=2/abs(2-phi-(phi*phi-4*phi)**0.5)
    
    #粒子速度の更新を行う
    if option!=0:
        new_v = [K * ( w * v[i] + c1 * random.uniform(0, ro_max) * (p[i] - x[i]) + c2 * random.uniform(0, ro_max) * (g[i] - x[i]) ) for i in range(dimension)]
    else:
        new_v = [w * v[i] + c1 * random.uniform(0, ro_max) * (p[i] - x[i]) + c2 * random.uniform(0, ro_max) * (g[i] - x[i]) for i in range(dimension)]

    return new_v

def main():
    w = 1.0
    w_best, w_worst = 1.25, 0.25
    x_min = [minimum for i in range(dimension)]
    x_max = [maximum for i in range(dimension)]
    
    #粒子位置, 速度, パーソナルベスト, グローバルベストの初期化を行う
    ps = [[random.randint(x_min[j], x_max[j]) for j in range(dimension)] for i in range(N)]
    vs = [[0.0 for j in range(dimension)] for i in range(N)]

    personal_best_positions = ps[:] 
    personal_best_scores = [criterion(p) for p in ps]

    if max_or_min == 1:
        best_particle = personal_best_scores.index(max(personal_best_scores))
    elif max_or_min == 0:
        best_particle = personal_best_scores.index(min(personal_best_scores))
    global_best_position = personal_best_positions[best_particle][:]

    for t in range(T):
        for n in range(N):
            x = ps[n][:]
            v = vs[n][:]
            p = personal_best_positions[n][:]

            if option>=2:
                best_list = sorted(personal_best_positions)
                mu = bisect.bisect_left( best_list, p ) + 1
                w = w_best - mu * (w_best - w_worst) / (N - 1)


            #粒子の位置の更新を行う
            new_x = update_position(x, v, x_min, x_max)
            ps[n] = new_x[:]

            #粒子の速度の更新を行う
            new_v = update_velocity(new_x, v, p, global_best_position, w)
            vs[n] = new_v[:]

            #評価値を求め, パーソナルベストの更新を行う
            score = criterion(new_x)

            if max_or_min == 1:
                if score > personal_best_scores[n]:
                    personal_best_scores[n] = score
                    personal_best_positions[n] = new_x[:]
            elif max_or_min == 0:
                if score < personal_best_scores[n]:
                    personal_best_scores[n] = score
                    personal_best_positions[n] = new_x[:]

        #グローバルベストの更新を行う
        if max_or_min == 1:
            best_particle = personal_best_scores.index(max(personal_best_scores))
            global_best_position = personal_best_positions[best_particle][:]

        elif max_or_min == 0:
            best_particle = personal_best_scores.index(min(personal_best_scores))
            global_best_position = personal_best_positions[best_particle][:]
                     
        f.write(str(max(personal_best_scores))+"\n")
    #最適解
    if max_or_min == 1:
        return max(personal_best_scores)
    elif max_or_min == 0:
        return min(personal_best_scores)

#--------------------------------------------------------------
with open('test_'+ str(option)+".txt", 'w') as f:
    
  if max_or_min == 1:
    best=-float("inf")
    for i in range(iter):
        best=max(best, main())

  elif max_or_min == 0:
    best=float("inf")
    for i in range(iter):
        best=min(best, main())

print(best)

Submission status: Accepted

Solution code:
'''
https://beta.atcoder.jp/contests/abc104/submissions/2954675
https://beta.atcoder.jp/contests/abc104/submissions/2953603
'''
D, G = map(int, input().split())
p = []
c = []
for i in range(D):
    x, y = map(int, input().split())
    p.append(x)
    c.append(y)

ans = max(p) * D
for i in range(1 << D):
    cnt = 0
    score = 0
    rest_max = -1
    for j in range(D):
        if i >> j & 1:
            score += c[j]
            score += p[j] * (j + 1) * 100
            cnt += p[j]
        else:
            rest_max = j
    if score < G:
        g = (rest_max + 1) * 100
        need = (G - score + g - 1) // g#Gを超えるのに必要な問題数
        if need >= p[rest_max]:
            continue#iで表されるコンプリートボーナス取得計画では、G以上を達成できない
        cnt += need
    ans = min(ans, cnt)
print(ans)

'''
G-score mod g: 剰余0～(g-1)
これに(g-1)を加えると
剰余は(g-1), g, ..., (2g-2) = (g+g-2)まで
元の剰余が0だった場合以外は、剰余をgで割ると1.xになるので、
整数部分を取れば、切り上げになっている
'''

Submission status: Accepted

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

ans = 10**9
for bit in range(1<<d):
    score = 0
    n = 0
    
    for i in range(d): 
        if bit & 1<<i: # Problems completely answered
            score += pc[i][1] + pc[i][0]*100*(i+1)
            n += pc[i][0]

    if score >= g:
        ans = min(ans, n)
    else: # additional answering
        for i in range(d-1, -1, -1): # answer from high-score problem
            if bit & 1<<i: # already answered completely
                continue
            for j in range(pc[i][0]): # answer to remaining problems
                if score >= g:
                    break
                score += 100*(i+1)
                n += 1
        ans = min(ans, n)

print(ans)

Submission status: Accepted

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

p = []

for i in range(d):
    p.append(list(map(int,input().split())))

from itertools import product
from math import ceil

ans = 1e09

for c in product([0,1],repeat=d):
    score = 0
    num = 0
    ind = 0
    for i in range(d):
        if c[i] == 1:
            score += p[i][0]*100*(i+1) + p[i][1]
            num += p[i][0]
        else:
            ind = max(i,ind)
    
    if g - score <= 0:
        ans = min(ans,num)
    elif g - score <= (p[ind][0]-1)*100*(ind+1):
        num += ceil((g-score)/(100*(ind+1)))
        ans = min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

D, G = reads()
p = [0] * D; c = [0] * D
for i in range(D):
  p[i], c[i] = reads()

def subsets(s):
  return 

def divceil(a, b):
  return (a + b - 1) // b

ans = sum(p)
for sub in chain(*(combinations(range(D), r) for r in range(D))):
  rest = G - sum((i+1) * 100 * p[i] + c[i] for i in sub)
  k = max(set(range(D)).difference(sub))
  if rest <= p[k] * (k+1) * 100:
    n = max(divceil(rest, (k+1) * 100), 0)
    ans = min(ans, sum(p[i] for i in sub) + n)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
pc = [[i + 1] + [int(x) for x in input().split()] for i in range(D)]

import math
m = {}
def f(cur, n, left):
    if left <= 0:
        return n
    def g(cur, n, left):
        if cur in m: return m[cur]
        r = m[cur] = f(cur, n, left)
        return r
    ret = 10**9
    for x in pc:
        i, p, c = x
        if (1 << i) & cur: continue
        ip = i*100*p
        if ip > left:
            h = math.ceil(left / (i*100))
            ret = min(ret, n + h)
        else:
            if n + p >= ret: continue
            h = g(cur | (1 << i), n + p, left - ip - c)
            ret = min(ret, h)
    return ret

print(f(0, 0, G))

Submission status: Accepted

Solution code:

D,G = map(int, input().split())

#prob_num = [3,5]
#comp = [500,800]

prob_num = []
comp = []

for i in range(D):
    p,c = map(int, input().split())
    prob_num.append(p)
    comp.append(c)

comp_point = []
for i in range(D):
    comp_point.append((100*(i+1)*prob_num[i]+comp[i]))



ans = 1000000
for b in range(1<<D):
    hasComp = []
    for j in range(D):
        if b & (1<<j):
            hasComp.append(True)
        else:
            hasComp.append(False)
        
    # compしてるものを決め打ち
    point = 0
    prb = 0
    for i in range(D):
        if hasComp[i]:
            point += comp_point[i]
            prb += prob_num[i]
    
    res = G-point
    
    while res>0:
        flag = 0
        for i in range(D-1,-1,-1):
            if not hasComp[i]:
                if res <= (100*(i+1)*(prob_num[i]-1)):
                    req_prob = (res//(100*(i+1))) + bool(res%(100*(i+1)))
                    prb += req_prob
                    res = 0
                    break
                
                else:
                    prb += (prob_num[i]-1)
                    res -= (100*(i+1))*(prob_num[i]-1)
        
            if i==0:
                flag = 1
                break
        
        if flag:
            break
    if res<=0:
        ans = min(ans,prb)
    
print(ans)

Submission status: Accepted

Solution code:
import sys

D, G = map(int, input().split())
pc = []
for i in range(D):
    pc.append(list(map(int, input().split())))

# print(pc)
ans = sys.maxsize
for i in range(2**D):
    S = bin(i)[2:]
    for j in range(D - len(S)):
        S = "0" + S
    # print(S)

    tmp_p = 0
    tmp_ans = 0
    max_k = 0
    for k in range(D):
        if(S[k:k+1] == "1"):
            tmp_p += pc[k][0] * 100 * (k + 1) + pc[k][1]
            tmp_ans += pc[k][0]
        else:
            if(max_k < k):
                max_k = k

    rest = G - tmp_p
    # print(G, tmp_p)
    if(rest >= 0):
        t = -(-1 * rest // (100 * (max_k + 1)))
        if(t < pc[max_k][0]):
            tmp_ans += t
            if(tmp_ans < ans):
                ans = tmp_ans
    else:
        if(tmp_ans < ans):
            ans = tmp_ans

print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
table=[(0,0) for i in range(D)]
for i in range(D):
    p,c=map(int,input().split())
    table[i]=(p,c)
ans=10**9

for i in range(1<<D):
    t=G
    s=0
    for j in range(D):
        if i & (1<<j):
            s+=table[j][0]
            t=t-table[j][1]-table[j][0]*(j+1)*100
    if t<=0:
        ans=min(ans,s)
        #print(i,s)
    else:
        j=D-1
        flag=True
        while flag and (j>=0):
            #print(i,j)
            if not (i & (1<<j)):
                for u in range(table[j][0]-1):
                    if t<=0:
                        flag =False
                        break
                    else:
                        s+=1
                        t-=100*(j+1)
            j-=1
        if t<=0:
            ans=min(ans,s)
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    d, g = map(int, input().split())
    p = []
    c = []
    for _ in range(d):
        p_i, c_i = map(int, input().split())
        p.append(p_i)
        c.append(c_i)

    # d = 2
    # g = 700
    # p = [3, 5]
    # c = [500, 800]

    # d = 5
    # g = 25000
    # p = [20, 40, 50, 30, 1]
    # c = [1000, 1000, 1000, 1000, 1000]

    ans = 10 * 100
    for bit in range(1 << d):
        sum_score = 0
        n_solved = 0
        # 1つも全完しないケースもこのfor文に含まれる
        for i in range(d):
            if bit & (1 << i) != 0:
                sum_score += c[i] + 100 * p[i] * (i + 1)
                n_solved += p[i]

        if g <= sum_score:
            ans = min(ans, n_solved)
            continue

        for i in range(d - 1, -1, -1):
            # already solved
            if bit & (1 << i) != 0:
                continue

            for j in range(p[i]):
                if g <= sum_score:
                    break
                sum_score += 100 * (i + 1)
                n_solved += 1

        ans = min(ans, n_solved)

    print(ans)

Submission status: Accepted

Solution code:
D,G=map(int,input().split())
answer=0
Q=[]
for i in range(D):
  p,c=map(int,input().split())
  answer+=p
  Q.append((i+1,p,c))
dp=[-10]*(answer+1)

dp[0]=0
for i,p,c in Q:
  for j in range(answer,-1,-1):
    for k in range(1,p+1):
      if k==p:
        cc=i*100*k+c
      else:
        cc=i*100*k
      if j-k>=0:
        dp[j]=max(dp[j],dp[j-k]+cc)
        
for i in range(answer+1):
  if dp[i]>=G:
    print(i)
    break

'''
from operator import itemgetter
import copy

D,G=map(int,input().split())

score=[]
scoreBonus=[]

answer=0
answerscore=G

for i in range(D):
  score.append(list(map(int,input().split())))
  scoreBonus.append([(i+1)*100,(i+1)*100,score[i][0],score[i][0]*(i+1)*100+score[i][1],0])
  
Bonus=copy.deepcopy(scoreBonus)
print(Bonus)



while(answerscore>0):
  Deletescore=[]
  
  
  
  for i in range(len(scoreBonus)):
    if scoreBonus[i][1]*scoreBonus[i][2]<=answerscore:
      scoreBonus[i][0]=(score[i][0]*(i+1)*100+score[i][1])//(score[i][0])
      scoreBonus[i][4]=1
    if scoreBonus[i][1]*scoreBonus[i][2]>answerscore:
      scoreBonus[i][0]=scoreBonus[i][1]
      scoreBonus[i][4]=0
    answerscore-=scoreBonus[i][3]
    answer+=scoreBonus[i][2]
    Deletescore.append(i)
  scoreBonus.sort(reverse=True)

  print(scoreBonus)
  print(Bonus)

  for i in range(len(scoreBonus)):
    count=scoreBonus[i][2]
    if scoreBonus[i][4]==1:
      answerscore-=scoreBonus[i][3]
      answer+=scoreBonus[i][2]
      count=0
      Deletescore.append(i)
      break;
    while(answerscore>0 and count!=0):
      answerscore-=scoreBonus[i][1]
      print(answerscore)
      answer+=1
      count-=1
    if answerscore<=0:
      print(answer)
      exit() 
  print(Deletescore)
  del scoreBonus[Deletescore[i]]
  print(scoreBonus)

print(answer)
print(scoreBonus)
if answerscore<=0:
  print(answer)
  exit()
  


scoreR=sorted(scoreBonus, key=itemgetter(1),reverse=True)
print(scoreR)
'''

Submission status: Accepted

Solution code:
import itertools
import math

D, G = map(int, input().split())

p = {}
c = {}
s = {}
for i in range(1, D + 1):
    pi, ci = map(int, input().split())
    score = 100 * i * pi + ci
    s[i] = score
    p[i] = pi
    c[i] = ci


def complete(pset):
    score = 0
    solved = 0
    comped = set()
    for i, b in zip(range(1, D + 1), pset):
        if b:
            score += s[i]
            solved += p[i]
            comped.add(i)
    leftset = set(list(range(1, D + 1))) - comped
    return score, solved, leftset


def left(norm, leftset):
    if norm <= 0 or len(leftset) == 0:
        return 0
    i = max(leftset)
    res = int(math.ceil(norm / (100 * i)))
    if res < p[i]:
        return res
    return float("inf")


ans = float("inf")
for pset in itertools.product((True, False), repeat=D):
    score, solved, leftset = complete(pset)
    solved += left(G - score, leftset)
    ans = min(ans, solved)

print(ans)

Submission status: Accepted

Solution code:
D, G = [int(_) for _ in input().split()]
PC = [[int(_) for _ in input().split()] for i in range(D)]
P = [p for p, c in PC]
C = [c for p, c in PC]

from heapq import *

h = []

heappush(h, (0, 0, (0,)*D))

result = 0

ef = {}

while h:
    t, score, pat = heappop(h)
    # print(t, score, pat)
    if score >= G:
        result = t
        break

    def add(i, pat, d):
        pat1 = list(pat)
        if pat1[i] +d <= P[i]:
            pat1[i] += d
            pat1 = tuple(pat1)
            if not pat1 in ef:
                t1 = t + d
                score1 = score + (i+1)*100*d
                if pat1[i] == P[i]:
                    score1 += C[i]
                ef[pat1] = t
                heappush(h, (t1, score1, pat1))

    for i in range(D-1, -1, -1):
        if pat[i] < P[i]:
            add(i, pat, 1)
            break

    for i in range(D):
        if pat[i] + 1 < P[i]:
            add(i, pat, P[i] - pat[i])

print(result)

Submission status: Accepted

Solution code:
D, G = map(int,input().split())
MAX = D*100+1
s = 1
g = D*100+1
z = [[0 for i in range(MAX)] for j in range(D+1)]
for i in range(1,D+1):
	p,c = map(int,input().split())
	for j in range(s):
		for k in range(p+1):
			z[i][j+k] = max(z[i][j+k],z[i-1][j]+100*k*i+(c if k == p else 0))
			if z[i][j+k] >= G and g > j+k:
				g = j+k
	s += p
print(g)

Submission status: Accepted

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

from math import ceil

D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)

cache = {}

def minsolve(G, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    n = min(ceil(G / (100 * i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    m = n if s >= G else n + minsolve(G - s, i-1)
    return min(m, minsolve(G, i-1))

print(minsolve(G, D))

Submission status: Accepted

Solution code:
import sys
from itertools import product

D, G = [int(i) for i in input().strip().split(' ')]
ps = []
cs = []
alls = []
vs = []
counter = 0
for line in sys.stdin:
    counter += 100
    p, c =[int(i) for i in line.strip().split(' ')]
    ps.append(p)
    cs.append(c)
    all = p * counter + c
    alls.append(all)
    vs.append(float(all)/p)

candidates = []
for x in  product([False, True], repeat=D):
    score = 0
    cnum = 0
    for count, bit in enumerate(x):
        if bit:
            score += alls[count]
            cnum += ps[count]
    if score >= G:
        candidates.append(cnum)
        continue
    for count, bit in enumerate(x[::-1]):
        if not bit:
            for xxx in range(ps[D-count-1]):
                score += (D-count) * 100
                cnum += 1
                if score >= G:
                    candidates.append(cnum)
                    break
print(min(candidates))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
from math import ceil
 
D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)
 
def minsolve(G, p, c, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    n = min(ceil(G / (100 * i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    if s >= G:
        return min(n, minsolve(G, p, c, i-1))
    else:
        return min(n + minsolve(G - s, p, c, i-1), minsolve(G, p, c, i-1))
 
m = min(minsolve(G, p, c, i) for i in range(1, D+1))
print(m)

Submission status: Accepted

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

def calcBit(n):
    res = []
    for i in range(d):
        res.append(n%2)
        n >>= 1
    return res[::-1]

res = float('inf')
for i in range(2**d):
    tmp = 0
    s = 0
    b = calcBit(i)
    for w,bit in enumerate(b):
        if bit==1:
            tmp += pa[w]
            s += pa[w]*(w+1)*100+ca[w]
    dif = g - s
    if dif>0:
        for j in range(len(pa)-1,-1,-1):
            if b[j]==0:
                t = dif//((j+1)*100)
                dif -= min(t,pa[j])*((j+1)*100)
                tmp += min(t,pa[j])
                if dif<=0:
                    break
    if dif<=0:
        res = min(res,tmp)
print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
inf = 1 << 30

d, g = [int(x) for x in input().split()]
p, c = zip(*[[int(x) for x in input().split()] for _ in range(d)])

def n_prob(l):
  t = sum([p[i]*(i+1)*100+c[i] for i in l])
  n = sum([p[i] for i in l])
  if t<g:
    for j in range(d-1, -1, -1):
      if j not in l:
        if t+p[j]*(j+1)*100 >= g:
          n += (g-t+(j+1)*100-1)//((j+1)*100)
          return n        
    return inf
  return n

print(min([n_prob(l) for x in range(d+1) for l in combinations(range(d), x) ]))