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:
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=sum(p)
for i in range(1<<d):
  a=[]
  cnt=0
  pt=0
  for j in range(d):
    if (i>>j)&1:
      pt+=p[j]*(j+1)*100+c[j]
      cnt+=p[j]
    else:a+=[(p[j],j+1)]
  if pt<g:
    j,k=a[-1]
    cnt+=(g-pt+k*100-1)//(k*100)
    pt+=k*100*j
  if pt>=g:ans=min(ans,cnt)
print(ans)

Submission status: Accepted

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

scoreList = [0 for i in range(D)]

for i in range(D):
    scoreList[i] = (i + 1) * 100 * pc[i][0] + pc[i][1]

choiceList = [[] for i in range(2 ** D)]
for i in range(2 ** D):
    for j in range(D):
        choiceList[i].append(i // (2 ** j) % 2)

minCount = 10 ** 8
for choice in choiceList:
    score = 0
    count = 0
    for i in range(len(choice)):
        if choice[i] == 1:
            score += scoreList[i]
            count += pc[i][0]
    for j in range(D):
        countTmp = count
        extraScore = (j + 1) * 100 * pc[j][0]
        delta = G - score
        if delta < 0:
            countTmp = count
        elif delta == 0:
            countTmp = count
        elif delta > 0:
            if delta <= extraScore and choice[j] == 0:
                countTmp += delta // ((j + 1) * 100)
                if delta % ((j + 1) * 100) > 0:
                    countTmp += 1
            else:
                countTmp = 10 ** 8
        if countTmp < minCount:
            minCount = countTmp
print(minCount)

Submission status: Accepted

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

ans = 100000000
for i in range(2**d):
  sub = 0
  count = 0
  complete = [False]*d
  for j in range(d):
    if (i>>j)&1:
      complete[j] = True
      sub += 100*(j+1)*point[j][0]+point[j][1]
      count += point[j][0]
  for j in range(d-1, -1, -1):
    if sub >= g:
      break
    if complete[j]:
      continue
    c = min((g-sub-1)//(100*(j+1))+1, point[j][0])
    count += c
    sub += c*100*(j+1)
    if c == point[j][0]:
      sub += point[j][1]
  if ans > count:
    ans = count

print(ans)

Submission status: Accepted

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

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


ans = 100*d*100
for d in itertools.product([0, 1], repeat=d):
    ans_tmp = 0
    value = 0

    for i, j in enumerate(d):
        if j == 0:
            continue
        ans_tmp += pc[i][0]
        value += (i+1)*100*pc[i][0] + pc[i][1]

    iter_ = [[i, j] for i, j in enumerate(d)]
    # print(iter_)
    for i, j in reversed(iter_):
        if j == 1:
            continue
        base = (i+1)*100

        shortage = g-value
        if g-value <= 0:
            break

        num = min(math.ceil(shortage/base), pc[i][0]-1)
        ans_tmp += num
        value += base*num
    # print(d)
    # print(value, ans_tmp)
    if value >= g:
        ans = min(ans, ans_tmp)

print(ans)

Submission status: Accepted

Solution code:
import math

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

ans = float("inf")

for bit in range(1 << D):
    count = 0
    sum = 0
    rest = list(range(1, D+1))

    for i in range(D):
        if bit & (1 << i):
            sum += (i + 1) * pc[i][0] * 100 + pc[i][1]
            count += pc[i][0]
            rest.remove(i + 1)

    if sum < G:
        max_num = max(rest)
        n = min(pc[max_num - 1][0], math.ceil((G - sum) / (max_num * 100)))
        count += n
        sum += n * max_num * 100

    if sum >= G:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

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

ans = float("inf")

for bit in range(1 << D):
    count = 0
    sum = 0
    rest = list(range(1, D+1))

    for i in range(D):
        if bit & (1 << i):
            sum += (i + 1) * pc[i][0] * 100 + pc[i][1]
            count += pc[i][0]
            rest.remove(i + 1)

    if sum < G:
        max_num = max(rest)
        n = min(pc[max_num - 1][0], -(-(G - sum) // (max_num * 100)))
        count += n
        sum += n * max_num * 100

    if sum >= G:
        ans = min(ans, count)

print(ans)

Submission status: Accepted

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


points = []
patterns = []
    
def flagfun(flag):
    if len(flag) == D:
        patterns.append(flag)
        return
    
    flagfun(flag+'0')
    flagfun(flag+'1')
    
def index_pattern():
    flagfun('')
    idxes = []
    for pattern in patterns:
        tmp_idx = []
        for idx, flag in enumerate(pattern):
            if flag == '1':
                tmp_idx.append(idx)
        idxes.append(tmp_idx)
    return idxes

def culc_points():
    for i, scores in enumerate(PC):
        max_score = (i+1)*scores[0]*100 + scores[1]
        points.append([scores[0], max_score])

culc_points()

idxes = index_pattern()
count = 1000000

for idx in idxes:
    tmp_count = 0
    tmp_score = 0
    remain_idx = [i for i in range(D)]
    for i in idx:
        tmp_count += points[i][0]
        tmp_score += points[i][1]
        num_index = remain_idx.index(i)
        remain_idx.pop(num_index)
           
    if tmp_count >= count:
        continue
    
    if tmp_score >= G:
        count = tmp_count
        continue
    
    max_idx = remain_idx.pop(-1)
    for i in range(1, points[max_idx][0]):
        tmp_count += 1
        tmp_score +=(max_idx+1)*100
        if tmp_count >= count:
            break
            
        if tmp_score >= G:
            count = tmp_count
            break

print(count)

Submission status: Accepted

Solution code:
def dfs(i, sum, count, rest):
    global ans
    if i == d:
        if sum < g:
            rest_max = max(rest)
            n = min(l[rest_max-1][0], -(-(g-sum)//(rest_max*100)))
            count += n
            sum += n * rest_max * 100
        if sum >= g:
            ans = min(ans, count)
    else :
        dfs(i+1, sum, count, rest) #二分岐のうち解かない選択
        dfs(i+1, sum + l[i][0]*(i+1)*100+l[i][1], count + l[i][0], rest - {i+1}) #解く選択

d, g = map(int, input().split())
l = [list((map(int, input().split()))) for _ in range(d)]
ans = float("inf")
dfs(0, 0, 0, set(range(1, d+1)))
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
L = []
for i in range(n):
    a,b = map(int,input().split())
    L.append([(i+1)*100,a,b])
#print(L)
ans = 10**10
if k < L[-1][0]*L[-1][1]:
    if k%L[-1][0] != 0:
        ans = (k//L[-1][0]+1)
    else:
        ans = (k//L[-1][0])

for i in range(1<<n):
    li = []
    score,score_zan,cnt = 0,0,0
    for j in range(n):
        if i>>j&1:
            score +=(L[j][0]*L[j][1] + L[j][2])
            cnt +=L[j][1]
            score_zan = k-score
        else:
            li.append(L[j])
    if score > 0 and score_zan <= 0:
        ans = min(ans,cnt)
    li.sort(reverse = True)
    #print(score,li,cnt,score_zan)
    if li and score_zan > 0:
        if score_zan < li[0][0]*li[0][1]:
            ans = min(ans,cnt + score_zan//li[0][0])
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p, c = list(zip(*[list(map(int, input().split())) for _ in range(D)]))

ans = sum(p)
for i in range(2 ** D):
    complete_indexes = [j for j in range(D) if (i >> j) & 1]

    cur_ans = 0
    cur_point = 0
    for j in complete_indexes:
        cur_ans += p[j]
        cur_point += p[j] * 100 * (j + 1) + c[j]

    if cur_point < G:
        incomplete_indexes = [j for j in range(D) if j not in complete_indexes]
        if incomplete_indexes:
            used_index = incomplete_indexes[-1]
            required = (G - cur_point + 100 * (used_index + 1) - 1) // (100 * (used_index + 1))
            cur_ans += min(required, p[used_index])
            cur_point += min(required, p[used_index]) * 100 * (used_index + 1)

    if G <= cur_point and cur_ans < ans:
        ans = cur_ans

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
p, c = list(zip(*[list(map(int, input().split())) for _ in range(D)]))

ans = sum(p)
for i in range(2 ** D):
    complete_indexes = [j for j in range(D) if (i >> j) & 1]

    question = 0
    point = 0
    for j in complete_indexes:
        question += p[j]
        point += p[j] * 100 * (j + 1) + c[j]

    if point < G:
        incomplete_indexes = [j for j in range(D) if j not in complete_indexes]
        if incomplete_indexes:
            index = incomplete_indexes[-1]
            required_question = (G - point + 100 * (index + 1) - 1) // (100 * (index + 1))
            question += min(required_question, p[index])
            point += min(required_question, p[index]) * 100 * (index + 1)

    if G <= point and question < ans:
        ans = question

print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
PC = [0]+[list(map(int,input().split())) for _ in range(D)]

def dfs(d, g):
    if(d == 0):
        return 1e9

    c = min(g//(100*d), PC[d][0])
    s = 100*d*c
    if c == PC[d][0]:
        s += PC[d][1]
    if s<g:
        c += dfs(d-1, g-s)
    return min(c, dfs(d-1,g))

print(dfs(D, G))

Submission status: Accepted

Solution code:
# 方針〜
# Dが10以下なのがポイント
# 全ての部分集合に対して「この集合を全問解いた場合、総合スコアをG点以上にするために何問解くか」をビット全探索すれば良い。
# Dividing Chocolate (ABC159-E)と似たようなもの

# なお、「この集合を全問解いた場合、総合スコアをG点以上にするために何問解くか」を解くときには
# 得点の高い方からGreedyだが、途中でコンプリートした時のボーナスを無視しても正しい答えは出せる。
# それ自体のスコアは間違いになるが、問題数が増える方向に間違うし、正しい部分集合のときには正しい問題数が得られるので。
# 今回は上記の方法でやってみる。

d, goal = list(map(int, input().split()))
problems = [list(map(int, input().split())) for _ in range(d)]

ans = 10 ** 6 * 10 * 2
for completed in range(2 ** d):
    
    point_all = 0
    num_problem = 0

    # 最下位のdigitが100点問題
    for point in range(d):
        if (completed & 2 ** point) > 0:
            point_all += 100 * (point+1) * problems[point][0]
            point_all += problems[point][1]
            num_problem += problems[point][0]
    
    if point_all < goal:
        for point in reversed(range(d)):
            if (completed & 2 ** point) == 0:
                p = (100 * (point+1))
                n = (goal - point_all + p - 1) // p
                n = min(problems[point][0], n)

                point_all += n * p  # ボーナス点は無視する
                num_problem += n

                if point_all >= goal:
                    break

    # 目標点数を達成しているとは限らないことに注意 条件に目標達成を入れる
    if point_all >= goal and num_problem < ans:
        ans = num_problem

print(ans)

Submission status: Accepted

Solution code:
from math import ceil
from itertools import product

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

def calc(P):
  count = 0
  g = G
  for i in range(D):
    p,c = pc[-1-i]
    if P[-1-i]==1:
      count += p
      g -= (D-i)*100*p+c
    if g<=0:
      return count
  for i in range(D):
    p,c = pc[-1-i]
    if P[-1-i]==0:
      tmp = min(p-1,ceil(g/((D-i)*100)))
      count += tmp
      g -= (D-i)*100*tmp
    if g<=0:
      return count
  return -1

MIN=10**9
for P in product(range(2),repeat=D):
  tmp = calc(P)
  if tmp != -1 and tmp < MIN: MIN=tmp
    
print(MIN)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
qu = [0] * D
bonus = [0] * D
for i in range(D):
  a, b = map(int, input().split()) 
  qu[i] = a
  bonus[i] = b
  
ans = 10 ** 5  
for i in range(2 ** D):
  score = 0
  nn = 0
  yet = [0] * D
  for j in range(D):#j の 問い をコンプリートする
    if (i >> j) & 1:
      score += 100 * (j + 1) * qu[j] + bonus[j]
      nn += qu[j]
      yet[j] = 1
  if score >= G:
    ans = min(ans, nn)
  else:
    #print(i, score, nn)
    con = 0
    for k in range(1, D + 1):
      if con == 0:
        if yet[D - k] == 0:
          now = 100 * (D - k + 1) * (qu[D - k] - 1)
          if now + score >= G:
            subt = G - score
            nn += int((subt - 1) / (100 * (D - k + 1))) + 1
            ans = min(ans, nn) 
            con = 1
          else:
            score += now
            nn += qu[D - k] - 1
  #print(ans)    
print(ans)

Submission status: Accepted

Solution code:
import math 
D, G = map(int, input().split())
K = [list(map(int, input().split())) for _ in range(D)]
G //= 100
def settify(i):
  s = []
  t = []
  for j in range(D):
    if i % 2 == 0:
      t.append(j)
    else:
      s.append(j)
    i = i>>1
    
  return s,t

ans = 10**20  
for i in range(2**D):
  s, t = settify(i)
  pt = sum([K[j][0]*(j+1)+K[j][1]//100 for j in s])
  tmp = sum([K[j][0] for j in s])
  #print(pt, G)
  #print(t)
  while pt < G and t:
    #print(min(K[t[-1]][0]-1,math.ceil((G-pt)/(t[-1]+1))),t[-1])
    tmp += min(K[t[-1]][0]-1,math.ceil((G-pt)/(t[-1]+1)))
    pt += min(K[t[-1]][0]-1,math.ceil((G-pt)/(t[-1]+1)))*(t[-1]+1)
    t.pop()
  #print(tmp,s,pt) 
  if pt < G:
    continue
  ans = min(ans, tmp)
    
print(ans)

Submission status: Accepted

Solution code:
n , g = map(int , input().split())
pt = []
for i in range(0 , n):
	pt.append(list(map(int , input().split())))
# u need to solve all the problems of some bitmask or 
# solve all the problems of the bitmask and if remaining solve the problem which has higher point
# and is not set 
ans = 10**9+89
for i in range(0 , (1<<n)):
	tot , cnt = 0 , 0 
	partial=-1
	for j in range(0 , n):
		if (i & (1<<j)):
			cnt = cnt+pt[j][0]
			tot = tot + (100)*(j+1)*pt[j][0]+pt[j][1]# solve all the problems
		else:
			partial =j# partial solve and take maximum of it because it is optimal
	if tot<g:# if points still remaining
		a = 100*(partial+1)
		rem = (g-tot+a-1)//a
		if rem>=pt[partial][0]:# ignore u can't solve this problem with this set of problems
			continue
		cnt =cnt+rem
	ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
d,g=map(int,input().split())
x=[list(map(int,input().split())) for i in range(d)]
y=[]
z=[x[i][0]-1 for i in range(d)]
zz=[]
ans=10**10

pin=0
for i in range(d):
  pin+=100
  y.append(x[i][0]*pin+x[i][1])
  zz+=[pin]

for lst in itertools.product(range(2),repeat=d):
  sum=0
  cnt=0
  for i in range(d):
    if lst[i]==1:
      cnt+=x[i][0]
      sum+=y[i]
  if sum>=g:
      ans=min(ans,cnt)
  else:
    lack=g-sum
    for j in range(d-1,-1,-1):
      if lst[j]==0:  
        if z[j]*zz[j]>=lack:
            cnt+=math.ceil(lack/zz[j])
            ans=min(ans,cnt)         
            break
        else:
            cnt+=z[j]
            lack-=z[j]*zz[j]
    

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
d,g=map(int,input().split())
x=[list(map(int,input().split())) for i in range(d)]
y=[]
z=[x[i][0]-1 for i in range(d)]
zz=[]
ans=10**10

pin=0
for i in range(d):
  pin+=100
  y.append(x[i][0]*pin+x[i][1])
  zz+=[pin]

for lst in itertools.product(range(2),repeat=d):
  sum=0
  cnt=0
  for i in range(d):
    if lst[i]==1:
      cnt+=x[i][0]
      sum+=y[i]
  if sum>=g:
      ans=min(ans,cnt)
  else:
    lack=g-sum
    for j in range(d-1,-1,-1):
      if lst[j]==0:  
        if z[j]*zz[j]>=lack:
            cnt+=math.ceil(lack/zz[j])
            lack=0
            break
        else:
            cnt+=z[j]
            lack-=z[j]*zz[j]
    if lack<=0:
      ans=min(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
d,g=map(int,input().split())
g=g//100
pc=[list(map(int,input().split())) for _ in range(d) ]
s=[0]*d
for i in range(d):
    p,c=pc[i]
    s[i]=(i+1)*p+c//100
n=2**d
ans=10**4
for i in range(0,n):
    res=0
    q=0
    for j in range(d):
        if i & (1<<j):
            res+=s[j]
            q+=pc[j][0]
    if g>res:
        q_b=q
        for j in range(d):
            if i & (1<<j):
                continue
            else:
                if (g-res)//(j+1)<pc[j][0]:
                    q_b=q+math.ceil((g-res)/(j+1))
                    ans=min(ans,q_b)
    else:
        ans=min(ans,q)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
p, c = [], []
for _ in range(d):
    tmp_p, tmp_c = map(int, input().split())
    p.append(tmp_p)
    c.append(tmp_c)

res = float('inf')
for i in range(2**d):
    num = 0
    score = 0
    flag = [False] * d
    for j in range(d):
        if (i >> j) & 1:
            num += p[j]
            score += 100 * (j + 1) * p[j] + c[j]
            flag[j] = True
    
    if score >= g:
        res = min(res, num)
        continue
    
    for j in range(d-1, -1, -1):
        if flag[j]:
            continue

        if score + 100 * (j + 1) * p[j] < g:
            num += p[j]
            score += 100 * (j + 1) * p[j]
            continue
        else:
            n = ((g - score) + (100 * (j + 1)) - 1) // (100 * (j + 1))
            num += n
            break
    
    res = min(res, num)

print(res)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
P = [list(map(int,input().split())) for d in range(D)]
ans = 1000

for i in range(1<<D):
  s=0
  n=0
  for j in range(D):
    if i>>j&1==1:
      s+=100*(j+1)*P[j][0]+P[j][1]
      n+=P[j][0]
  for j in range(D-1,-1,-1):
    if i>>j&1==0:
      r = ((G-s)//100+j)//(j+1)
      if r>P[j][0]:
        n = 1000
      else:
        n+=max(r,0)
      break
  ans=min(ans,n)

print(ans)

Submission status: Accepted

Solution code:
d , g = map(int,input().split())
poi = [tuple(map(int,input().split())) for i in range(d)]
ans = 10**5
for i in range(2**d):
    cou = 0
    ten = 0
    for j in range(d):
        if i >> j & 1 == 1:
            cou += poi[j][0]
            ten += poi[j][1] + (j+1)*100*poi[j][0]
    for j in reversed(range(d)):
        if ten >= g:
            break
        if i >> j & 1 != 1:
            if g - ten > (j+1)*100*(poi[j][0]-1):
                cou += poi[j][0] - 1
                ten += (j+1)*100*(poi[j][0]-1)
            elif g - ten <= (j+1)*100*(poi[j][0]-1):
                cou -= (ten-g)//((j+1)*100)
                ten = g
                break
    if ten >= g:
        ans = min(ans,cou)
print(ans)

Submission status: Accepted

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


def dfs(i, sum, count, nokori):
    global ans
    if i == d:#全ての最後の問題セットにたどり着いたら,　全ての葉を確認
        if sum < g:
            use = max(nokori)#選んでいない種類で最大のスコアの問題を選ぶ
            #-(-(g-sum)//(use*100)) <- (g-sum)//(use*100)
            n = min(pc[use-1][0], -(-(g-sum)//(use*100)))#その難易度の問題の数 または 残りの必要スコア/その難易度の問題1問の点数　の最小値をとる->余計に問題を解かない＆問題数を超えてとかない
            count += n
            sum += n * use * 100

        if sum >= g:#全ての葉の達成してる最小の答えを記録
            ans = min(ans, count)

    else:
        dfs(i+1, sum, count, nokori)#選ばなかった場合
        dfs(i+1, sum + pc[i][0] * (i+1) * 100 + pc[i][1], count + pc[i][0], nokori - {i+1})#全て解いた番号をセットから抜いて、合計&countを更新

ans = float("inf")
dfs(0, 0, 0, set(range(1, d+1)))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
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
for i in range(1 << D):
    points = 0
    solved = 0
    for j in range(D):
        if i & 1 << j > 0:
            points += C[j]
            points += P[j] * (j + 1) * 100
            solved += P[j]

    left = G - points
    for j in range(D - 1, -1, -1):
        if left <= 0:
            break
        if i & 1 << j > 0:
            continue
        val = min(100 * (j + 1) * (P[j] - 1), left)
        left -= val
        if val % (100 * (j + 1)) != 0:
            solved += val // (100 * (j + 1)) + 1
        else:
            solved += val // (100 * (j + 1))

    if left > 0:
        continue
    ans = min(ans, solved)
print(ans)

Submission status: Accepted

Solution code:
D, G = map(int, input().split())
T = []
acc = 0
for i in range(D):
    p, c = map(int, input().split())
    acc += p
    T.append([p, c])
dp = [[0]*(acc+1) for _ in range(D+1)]
l = 0
for i in range(1, D + 1):
    for j in range(1, acc + 1):
        l += T[i-1][0]
        for k in range(T[i-1][0] + 1):
            if j <= l and j - k >= 0:
                if k == T[i-1][0]:
                    dp[i][j] = max([dp[i - 1][j - k] + 100 * i * k + T[i - 1][1], dp[i - 1][j]])
                else:
                    dp[i][j] = max([dp[i - 1][j - k] + 100 * i * k, dp[i - 1][j]])

for i in range(acc + 1):
    if dp[D][i] >= G:
        print(i)
        break

Submission status: Accepted

Solution code:
import itertools
D, G = [int(_) for _ in input().split()]
SPC = [[100 * (i + 1)] + [int(_) for _ in input().split()]
       for i in range(D)][::-1]
ans = 10**10
for i in range(D + 1):
    completes = set(itertools.combinations(range(D), i))
    for complete in completes:
        incomplete = sorted(set(range(D)) - set(complete))
        score = 0
        cnt = 0
        f = 0
        for j in complete:
            s, p, c = SPC[j]
            score += s * p + c
            cnt += p
        for j in incomplete:
            if score >= G:
                break
            s, p, c = SPC[j]
            d = min(p - 1, 1 + (G - score - 1) // s)
            score += s * d
            cnt += d
        if score >= G:
            ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
d, g = map(int, input().split())
pc = [tuple(map(int, input().split())) for _ in range(d)]
ans = 1001001001
for s in range(1 << d):
    now = 0
    rest = g
    for i in range(d):
        if s >> i & 1:
            p, c = pc[i]
            rest -= p * (i+1) * 100 + c
            now += p
    if rest > 0:
        free = d-1
        while d >= 0 and s >> free & 1:
            free -= 1
        if free < 0:
            continue
        t = (rest + (free+1) * 100 - 1) // ((free+1) * 100)
        #print(rest,t)
        if t >= pc[free][0]:
            continue
        now += t
    ans = min(ans, now)
print(ans)

Submission status: Accepted

Solution code:
D,G = map(int,input().split())
pc = [list(map(int,input().split())) for i in range(D)]
ans = float('inf')
for bit in range(1<<D):
    _sum = 0
    _ans = 0
    rest = [i for i in range(D)]
    for i in range(D):
        if bit & (1<<i):
            _sum += pc[i][0]*(i+1)*100 + pc[i][1]
            _ans += pc[i][0]
            rest.remove(i)
    if _sum < G and len(rest) != 0:
        i = max(rest)
        for j in range(pc[i][0]-1):
            _sum += (i+1)*100
            _ans += 1
            if _sum >= G:
                break
    if _sum >= G:
        ans = min(ans,_ans)
print(ans)

Submission status: Accepted

Solution code:
d,g=map(int,input().split())
v=[list(map(int,input().split())) for i in range(d)]
ans=1000
for i in range(1<<d):
  s=0
  n=0
  for j in range(d):
    if i>>j&1 == 1:
      s += v[j][0] * (j+1) * 100 + v[j][1]
      n += v[j][0]
  for j in range(d-1,-1,-1):
    if i>>j&1 == 0:
      r = ((g-s)//100 + j) // (j+1)
      if r>v[j][0]:
        n = 1000
      else:
        n += max(r,0)
      break
  ans=min(ans,n)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

D, G, *pc = map(int, open(0).read().split())
pc = list(zip(*[iter(pc)]*2))
p, c = np.array([]), np.array([])
for (x,y) in pc:
    p = np.append(p, x)
    c = np.append(c, y)
    
import numpy as np
import math

base_points = np.array([i*100 for i in range(1, D+1)])

ans = []

for i in range(2**D):
    bit_flag = np.array(list(map(int, format(i, '0%db' %D))))
    points = sum(bit_flag * (c + p*base_points))
    solved_num = sum(bit_flag * p)
    
    if points >= G:
        ans.append(solved_num)

    else:
        remained = G - points
        remained_problems = sorted((bit_flag==False) * np.array(range(1, D+1)), reverse=True)
        i = 0

        while True:
            if remained <= 0:
                break
                
            highest_p = remained_problems[i]

            if math.ceil(remained / (highest_p * 100)) <= p[highest_p - 1]:
                solved_num += math.ceil(remained / (highest_p * 100))
                remained -= (math.ceil(remained / (highest_p * 100)) * highest_p * 100)
            else:
                solved_num += p[highest_p - 1]
                remained -= (highest_p * 100 * p[highest_p - 1] + c[highest_p - 1])
                i += 1

        ans.append(solved_num)
        
print(int(min(ans)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]
ans = 10**8
for p in product((0, 1), repeat=D):
    nmax = -1
    num = 0
    total = 0
    need = 0
    for i, pi in enumerate(p):
        if pi == 1:
            num += pc[i][0]
            total += pc[i][0]*(i+1)*100 + pc[i][1]
        else:
            nmax = i
#     print(p)
#     print(nmax, num, total)
    if total < G:
        if nmax < 0:
            continue
        if total + nmax * 100 * pc[nmax][0] + pc[nmax][1] < G:
            continue
        need = math.ceil((G-total) / ((nmax+1)*100))
    ans = min(ans, num+need)
#     print(nmax, num, total, need, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import collections
import copy
from collections import deque 
from functools import reduce
from itertools import product

# input = sys.stdin.readline

D, G = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(D)]
ans = 10**8
for p in product((0, 1), repeat=D):
    nmax = -1
    num = 0
    total = 0
    need = 0
    for i, pi in enumerate(p):
        if pi == 1:
            num += pc[i][0]
            total += pc[i][0]*(i+1)*100 + pc[i][1]
        else:
            nmax = i
#     print(p)
#     print(nmax, num, total)
    if total < G:
        if nmax < 0:
            continue
        if total + nmax * 100 * pc[nmax][0] + pc[nmax][1] < G:
            continue
        need = (G - total + ((nmax+1)*100-1)) // ((nmax+1)*100)
    ans = min(ans, num+need)
#     print(nmax, num, total, need, ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  ans = 2000
  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())
  for p in product([0,1],repeat=D):
    if sum(p)<D:
      for i in range(D-1,-1,-1):
        if p[i]==0:
          maxi = i
          break
    cnt = 0
    score = 0
    for i in range(D):
      if p[i]==1:
        score += (i+1)*100*P[i]+C[i]
        cnt += P[i]  
    if -(-(G-score)//(100*(maxi+1)))>=P[maxi]:
      continue
    if G>score:
      cnt += -(-(G-score)//(100*(maxi+1)))
    ans = min(ans,cnt)
  return ans
print(solve())

Submission status: Accepted

Solution code:
import math

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

ans = float("inf")
for i in range(1 << d):
    score = 0
    took = 0
    not_took = []
    for j in range(d):
        p, c = pc[j]
        if i & 1 << j:
            score += (j + 1) * 100 * p + c
            took += p
        else:
            not_took.append(j)
    if score >= g:
        ans = min(ans, took)
    elif len(not_took) != 0:
        last = not_took[-1]
        need = math.ceil((g - score) / ((last + 1) * 100))
        if need <= pc[last][0]:
            ans = min(ans, took+need)
print(ans)

Submission status: Accepted

Solution code:
import collections

d,g =  map(int, raw_input().split())
cc = {0:0}
picis = [map(int,raw_input().split()) for _ in range(d)]

pisum = sum([pi for pi,ci in picis] or [0])
for i in range(len(picis)):
	pi,ci = picis[i]
	for p in range(1, pisum + 1)[::-1]:
		for q in range(1, pi + 1):
			if p - q >= 0 and (p - q) in cc:
				cc[p] = max(cc[p] if p in cc else -float('inf'),  cc[p - q] + (100 * q * (i + 1)) + (ci if pi == q else 0))

for k in range(pisum+1):
	if cc[k] >= g:
		print k
		break