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
MAX_DEPTH  = 1000000000000
give_up = MAX_DEPTH
def solve(rest, score, depth, i):
    global give_up
    if give_up <= depth:
        return 
    score += 100 * (i + 1)
    rest[i] -= 1
    depth += 1
    if rest[i] == 0:
        score += c[i]
    if G <= score:
        return depth
    else:
        all_depth = [MAX_DEPTH]
        min_ans = MAX_DEPTH
        for j in range(0, D):
            if rest[i] != 0:
                ans = solve(copy.deepcopy(rest), score, depth, j)
                if ans and ans <= min_ans:
                    min_ans = ans
                    give_up = ans
        return min_ans
 
D,G = [int(x) for x in input().split()]
c = []
rest = []
for _ in range(D):
    _p, _c = [int(x) for x in input().split(" ")]
    rest.append(_p)
    c.append(_c)
results = []
for h in range(D):
  results.append(solve(copy.deepcopy(rest), 0, 0, h))
print(min(results))

Submission status: Time Limit Exceeded

Solution code:
import copy
MAX_DEPTH  = 1000000000000
def solve(rest, score, depth, i, give_up=MAX_DEPTH):
    if give_up <= depth:
        return 
    score += 100 * (i + 1)
    rest[i] -= 1
    depth += 1
    if rest[i] == 0:
        score += c[i]
    if G <= score:
        return depth
    else:
        all_depth = [MAX_DEPTH]
        min_ans = MAX_DEPTH
        for j in range(0, D):
            if rest[i] != 0:
                ans = solve(copy.deepcopy(rest), score, depth, j, min_ans)
                if ans and ans <= min_ans:
                    min_ans = ans
        return min_ans
 
D,G = [int(x) for x in input().split()]
c = []
rest = []
for _ in range(D):
    _p, _c = [int(x) for x in input().split(" ")]
    rest.append(_p)
    c.append(_c)
results = []
for h in range(D):
  results.append(solve(copy.deepcopy(rest), 0, 0, h))
print(min(results))

Submission status: Time Limit Exceeded

Solution code:
import copy
def solve(rest, score, depth, i):
    score += 100 * (i + 1)
    rest[i] -= 1
    depth += 1
    if rest[i] == 0:
        score += c[i]
    if G <= score:
        return depth
    else:
        all_depth = [100]
        for j in range(0, D):
            if rest[i] != 0:
                all_depth.append(solve(copy.deepcopy(rest), score, depth, j))
        return min(all_depth)

D,G = [int(x) for x in input().split()]
c = []
rest = []
for _ in range(D):
    _p, _c = [int(x) for x in input().split(" ")]
    rest.append(_p)
    c.append(_c)
results = []
for h in range(D):
  results.append(solve(copy.deepcopy(rest), 0, 0, h))
print(min(results))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

D,G = map(int,input().split(" "))
p = []
c = []
score_list = []
for i in range(D):
    p_,c_ = map(int,input().split(" "))
    p.append(p_)
    c.append(c_)
    for n in range(p_):
        score_list.append((i+1)*100)

ans = sum(p)

if min(c) >= G:
    count = 0
    score = 0
    for j in range(D - 1, -1, -1):
        for k in range(p[j] - 1):
            score += (j + 1) * 100
            count += 1

            if score >= G:
                ans = min(ans, count)
                break
        if score >= G:
            break
else:
    # 何個の問題をコンプリートボーナス取得まで解くかのループ
    for i in range(1,len(score_list)):

        # コンプリートボーナスの組み合わせ
        comp_scores_pos = list(itertools.combinations(np.arange(len(c)),i))

        for cs in comp_scores_pos:        
            # 合計を計算（コンプリートボーナス）
            cs = list(cs)
            if len(cs) <= 1:
                score = c[cs[0]]
            else :
                score = sum(np.array(c)[cs])

            # 合計を計算（問題の得点）と問題数のカウント
            count = 0
            for n in cs:
                score += (n + 1) * 100 * p[n]
                count += p[n]

            # G以上か見て
            if score >= G:
                # 最小値を更新
                ans = min(ans, count)
    #             print("ans = ", ans, ", count = ", count, ", cs = ", cs)
            else:
#                 print("cs = ", cs, ", score = ", score, ", count = ", count)
                # 何個の問題を解けばGに届くか
                for j in range(D - 1, -1, -1):
                    for k in range(p[j] - 1):
                        if cs.count(j) > 0:
                            continue

                        score += (j + 1) * 100

#                         print("j = ", j, ", score = ", score)
                        count += 1

                        if score >= G:
                            ans = min(ans, count)
#                             print("ans = ", ans, ", count = ", count, ", cs = ", cs)
                            break
                    if score >= G:
                        break
#                 print()
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
D, G = [int(v) for v in input().split()]
P = []
C = []
for i in range(D):
    p, c = [int(v) for v in input().split()]
    P.append(p)
    C.append(c)

l = itertools.permutations(range(1, D + 1), D)
r = []
for l2 in l:
    score = 0
    cnt = 0
    flg = False
    for i in l2:
        for j in range(P[i - 1]):
            score += i * 100
            if j == P[i - 1] - 1:
                score += C[i - 1]
            cnt += 1
            if score >= G:
                r.append(cnt)
                flg = True
                break
        if flg:
            break
print(min(r))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
d, g = map(int, input().split())
data = []
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in range(len(targets)):
    p, c, score, subtotal = data[targets[i]]
    t = (total + score - 1) // score
    if t < p and t < result:
      result = t
    t = p + f(data, total - subtotal, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
d, g = map(int, input().split())
data = []
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = data[i][2]
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c, score, subtotal = data[j]
    t = p + f(data, total - subtotal, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
d, g = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(d)]
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = (i + 1) * 100
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c = data[j]
    t = p + f(data, total - (j + 1) * 100 * p - c, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
INF = float('inf')
d, g = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(d)]
def f(data, score, targets):
  if score <= 0:
    return 0
  result = INF
  for i in targets:
    t = ceil(score / ((i + 1) * 100))
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c = data[j]
    t = p + f(data, score - (j + 1) * 100 * p - c, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
INF = float('inf')
d, g = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(d)]
def f(data, score, targets):
  if score <= 0:
    return 0
  result = INF
  for i in targets:
    t = ceil(score / ((i + 1) * 100))
    if t < data[i][0]:
      result = min(result, t)
  for i in range(len(targets)):
    j = targets[i]
    x = (j + 1) * 100 * data[j][0] + data[j][1]
    t = data[j][0] + f(data, score - x, targets[0:i] + targets[i + 1:])
    result = min(result, t)
  return result
print(f(data, g, list(range(len(data)))))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

D,G = map(int,input().split(" "))
p = []
c = []
score_list = []
for i in range(D):
    p_,c_ = map(int,input().split(" "))
    p.append(p_)
    c.append(c_)
    for n in range(p_):
        score_list.append((i+1)*100)
        
ans = sum(p)

for i in range(1,len(score_list)):
    takahashi_kaitou = set(itertools.combinations(score_list, i))
    
    for tk in takahashi_kaitou:
        counter = collections.Counter(tk)
        
        # 合計を計算
        score = sum(tk)
        
        # コンプリートボーナス足す
        for key,value in counter.items():
            index = int(key / 100 - 1)
            if p[index] == value:
                score += c[index]
        
        # G以上か見て
        if score >= G:
            tk_length = len(tk)
            
            # G以上だったらtkの個数数えて、最小値を更新
            if ans > tk_length:
                ans = tk_length
print(ans)

Submission status: Time Limit Exceeded

Solution code:
D, G = map(int, input().split())
scores = []
bonus = []
for i in range(1, 1 + D):
    p, c = map(int, input().split())
    bonus.append([c, (2 ** p) - 1 << len(scores)])
    scores += [i * 100] * p

n = len(scores)
bit = 0
problems = []
while bit < (1 << n):
    total_score = 0
    problem = 0
    # add score
    for i in range(n):
        if bit & 1 << i:
            total_score += scores[i]
            problem += 1
    # add bonus
    for c, bb in bonus:
        if (bit & bb) == bb:
            total_score += c

    if G <= total_score:
        problems.append(problem)

    bit += 1

print(min(problems))

Submission status: Time Limit Exceeded

Solution code:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for _ in range(d)]
n = sum([pc[i][0] for i in range(d)])
prob = []
comp = [0 for _ in range(len(pc))]
for i in range(len(pc)):
    prob += [100*(i+1)] * (pc[i][0])
for i in range(len(pc)):
    comp[i] = pc[i][0]
ans = float('inf')
for i in range(2 ** n):
    total = 0
    comp_bag = [0 for _ in range(len(comp))]
    count = 0
    for j in range(n):
        if (i>>j) & 1:
            total += prob[j]
            comp_bag[prob[j]//100-1] += 1
        if comp_bag[prob[j]//100-1] == comp[prob[j]//100-1] and count == 0:
            total += pc[prob[j]//100-1][1]
            count += 1

    if total >= g:
        ans = min(ans, sum(comp_bag))
    #print(total, comp_bag)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

D,G = II()
p,c = Line(D)

def dfs(point,p):
    if point<=0:
        return 0
    else:
        ret = []
        for i in range(D):
            if p[i]==0:
                continue
            num = math.ceil(point/((i+1)*100))
            if num <= p[i]:
                ret.append(num)
            else:
                temp = p[i]
                p[i] = 0
                ret.append(dfs(point-100*(i+1)*temp-c[i],p)+temp)
                p[i] = temp
        return min(ret)

print(dfs(G,p))

Submission status: Time Limit Exceeded

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

D,G = II()
p,c = Line(D)

def dfs(point,p):
    if point<=0:
        return 0
    else:
        ret = []
        for i in range(D):
            if p[i]==0:
                continue
            if math.ceil(point/((i+1)*100)) <= p[i]:
                ret.append(math.ceil(point/((i+1)*100)))
            else:
                temp = p[i]
                p[i] = 0
                ret.append(dfs(point-100*(i+1)*temp-c[i],p)+temp)
                p[i] = temp
        return min(ret)

print(dfs(G,p))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    g, list_of_p_and_c = read()
    result = think(g, list_of_p_and_c)
    write(result)


def read():
    d, g = read_int(2)
    list_of_p_and_c = []
    for i in range(d):
        list_of_p_and_c.append(read_int(2))
    return g, list_of_p_and_c


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(g, list_of_p_and_c):
    complete_bonus = []
    list_of_question_remained = []
    for p, c in list_of_p_and_c:
        list_of_question_remained.append(p)
        complete_bonus.append(c)

    return recursive_call(g, complete_bonus, list_of_question_remained, 0, 0, {})


def recursive_call(g, complete_bonus, list_of_question_remained, questions_solved, subsum, cache):
    key = generate_key_for(list_of_question_remained)
    if key in cache:
        return cache[key]

    if subsum >= g:
        return questions_solved

    max_p = 100
    max_d = 10

    minimum_questions_should_be_solved = max_p * max_d + 1
    for i in range(len(list_of_question_remained)):
        if list_of_question_remained[i] == 0:
            continue
        local_list_of_question_remained = list(list_of_question_remained)
        local_list_of_question_remained[i] -= 1
        if local_list_of_question_remained[i] == 0:
            minimum_questions_should_be_solved = min(minimum_questions_should_be_solved, recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + 1, subsum + 100 * (i + 1) + complete_bonus[i], cache))
        else:
            minimum_questions_should_be_solved = min(minimum_questions_should_be_solved, recursive_call(g, complete_bonus, local_list_of_question_remained, questions_solved + 1, subsum + 100 * (i + 1), cache))

    cache[key] = minimum_questions_should_be_solved
    return minimum_questions_should_be_solved


def generate_key_for(list_of_question_remained):
    return ','.join(map(str, list_of_question_remained))


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

p = []
c = []
for i in range(D):
    pi, ci = map(int, input().split())
    p.append(pi)
    c.append(ci)
    
score = []
for i in range(D):
    scorei = [(i + 1) * 100] * p[i]
    score.extend(scorei)
    
min_count = len(score)
for i in range(1 << len(score)):
    score_list = []
    for j in range(len(score)):
        if ((i >> j) & 1) == 1:
            score_list.append(score[j])
    total = sum(score_list)
    
    for j in range(D):
        if score_list.count((j + 1) * 100) == p[j]:
            total += c[j]
    
    if total >= G:
        min_count = min(min_count, len(score_list))
        
    if min_count == 1:
        break
        
print(min_count)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))
 
big = 9999999
 
probably_ans = big
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    if pt >= G:
        return depth
    if depth >= probably_ans or index > D:  # 遅いかも
        return big
    
    # 一つも引かない
    probably_ans = min(probably_ans, hogehoge(depth, index + 1, pt, left, bonus, probably_ans))
    
    # 全部引いて index reset
    for k in range(0, D - index + 1):
        if left[index + k]:
            temp = left[index + k]
            left[index + k] = 0
            probably_ans = min(probably_ans, hogehoge(depth+temp, 1, pt + (index + k) * 100 * temp + bonus[index + k], left, bonus, probably_ans))
            left[index + k] = temp

    # 歯抜け状態から行けそうならクリア
    if left[index]:
        if pt + index * 100 * left[index] + bonus[index] >= G:
            for i in range(1, left[index] + 1):
                left[index] = left[index] - i
                new_pt = pt + index * 100 * i + bonus[index] * (left[index] == 0)
                if (new_pt >= G):
                    probably_ans = min(probably_ans, hogehoge(depth+i, index+1, new_pt, left, bonus, probably_ans))
                left[index] = left[index] + i
    return probably_ans
    
print(hogehoge(0, 1, 0, left, bonus, probably_ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
D, G = list(map(int, input().split(' ')))
left = {}
bonus = {}
for i in range(1, D+1):
    left[i], bonus[i] = list(map(int, input().split(' ')))

big = 9999999

probably_ans = big
def hogehoge(depth, index, pt, left, bonus, probably_ans):
    if depth >= probably_ans:  # 遅いかも
        return big
    if pt >= G:
        return depth
    for i in range(index, 0, -1):
        if left[i] == 0:
            continue
        left[i] = left[i] - 1
        probably_ans = min(probably_ans, hogehoge(depth+1, i, pt + i * 100 + bonus[i] * (left[i] == 0), left, bonus, probably_ans))
        left[i] = left[i] + 1
    return probably_ans
    
print(hogehoge(0, D, 0, left, bonus, probably_ans))

Submission status: Time Limit Exceeded

Solution code:
D, G = map(int, input().split())
P = []
C = []
A = []
for i in range(D):
  p, c = map(int, input().split())
  for j in range(p - 1):
    P.append((i + 1) * 100 * (j + 1))
    C.append(j + 1)
    A.append(i + 1)
  P.append((i + 1) * 100 * p + c)
  C.append(p)
  A.append(i + 1)
  
out = 1000
for i in range(2**len(P)):
  total = 0
  count = 0
  solved = []
  for j in range(len(P)):
    if i & (1 << j):
      if A[j] not in solved:
        total += P[j]
        count += C[j]
        solved.append(A[j])
  if total >= G:
    if count < out:
      out = count
print(out)

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

min_solved = 1000

def dfs(depth, solve_num, point, sum_solved):
    global min_solved

    point += (depth+1) * 100 * solve_num
    if solve_num == p[depth]:
        point += c[depth]
    
    if point >= G:
        if sum_solved < min_solved:
            min_solved = sum_solved
        return 0

    if depth == len(p) - 1:
        return 0

    for i in range(p[depth+1]+1):
        dfs(depth+1, i, point, sum_solved + i)

    return 0

for i in range(p[0]+1):
    dfs(0, i, 0, i)

print(min_solved)
print("\n")

Submission status: Time Limit Exceeded

Solution code:
def solve(levelNum, levelProblemNums, extraPoints, target):
	target = int(target / 100)
	dp = [[99999999] * (target+1) for _ in range(levelNum+1)]
	for i in range(levelNum+1):
		dp[i][0] = 0
	#print(dp)
	#print(target)
	#return 0
    # for each level
	for l in range(1, levelNum+1):
		#for each point

		for point in range(1, target+1):
			dp[l][point] = dp[l-1][point]
			for p in range(1, levelProblemNums[l-1]+1):
				curPoint = p*l if p < levelProblemNums[l-1] else p*l + int(extraPoints[l-1]/100)
				subPoint = point - curPoint if point > curPoint else 0
				dp[l][point] = min(dp[l-1][subPoint]+p, dp[l][point])
				if subPoint == 0: break;

	return dp[l][target]	

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)

rt = solve(D, P, C, G)
print(rt)

Submission status: Time Limit Exceeded

Solution code:
def solve(levelNum, levelProblemNums, extraPoints, target):
	target = int(target / 100)
	dp = [[99999999] * (target+1) for _ in range(levelNum+1)]
	for i in range(levelNum+1):
		dp[i][0] = 0
	#print(dp)
	#print(target)
    # for each level
	for l in range(1, levelNum+1):
		#for each point
		#print( l)
		for point in range(1, target+1):
			dp[l][point] = dp[l-1][point]
			for p in range(1, levelProblemNums[l-1]+1):
				curPoint = p*l if p < levelProblemNums[l-1] else p*l + int(extraPoints[l-1]/100)
				subPoint = point - curPoint if point > curPoint else 0
				dp[l][point] = min(dp[l-1][subPoint]+p, dp[l][point])
				if subPoint == 0: break;

	return dp[l][target]	

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)

rt = solve(D, P, C, G)
print(rt)

Submission status: Time Limit Exceeded

Solution code:
def solve(levelNum, levelProblemNums, extraPoints, target):
	target = int(target / 100)
	dp = [[99999999] * (target+1) for _ in range(levelNum+1)]
	for i in range(levelNum+1):
		dp[i][0] = 0
	#print(dp)
	#print(target)
    # for each level
	for l in range(1, levelNum+1):
		#for each point
		#print( l)
		for point in range(1, target+1):
			dp[l][point] = dp[l-1][point]
			for p in range(1, levelProblemNums[l-1]+1):
				curPoint = p*l if p < levelProblemNums[l-1] else p*l + int(extraPoints[l-1]/100)
				subPoint = point - curPoint if point > curPoint else 0
				dp[l][point] = min(dp[l-1][subPoint]+p, dp[l][point])

	return dp[l][target]	

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)

#res = [D]
rt = solve(D, P, C, G)
print(rt)

Submission status: Time Limit Exceeded

Solution code:
def dfs(res, depth, path, P, C, G):
    if sum((index+1)*100 for index in path) >= G:
        res[0] = min(res[0], len(path))
        return
    elif depth == len(C):
        return
    for j in range(P[depth]+1):
        if j == P[depth]:
            dfs(res, depth+1, path + [depth] * j, P, C, G-C[depth])
        else:
            dfs(res, depth+1, path + [depth] * j, P, C, G)

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)

res = [sum(P)]
dfs(res, 0, [], P, C, G)
print(res[0])

Submission status: Time Limit Exceeded

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

kumiawase = []
def total(li):
    total = 0
    for ind, zip_ in enumerate(zip(li, plist, clist), start=1):
        l, p, c = zip_
        total += l*(100*ind)
        if l == p:
            total +=c
    return total

def dfs(D, li):
    if D == d:
        if total(li)>=g:
            global kumiawase
            kumiawase.append(li)
    else:
        for solve_num in range(plist[D] + 1):
            dfs(D+1, li + [solve_num])

dfs(0, [])
ans = kumiawase[0]
for k in kumiawase:
    if sum(k) < sum(ans):
        ans = k
print(sum(ans))

Submission status: Time Limit Exceeded

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

kumiawase = []
def dfs(D, li):
    if D == d:
        global kumiawase
        kumiawase.append(li)
    else:
        for solve_num in range(plist[D] + 1):
            dfs(D+1, li + [solve_num])


def total(li):
    total = 0
    for ind, zip_ in enumerate(zip(li, plist, clist), start=1):
        l, p, c = zip_
        total += l*(100*ind)
        if l == p:
            total +=c
    return total

dfs(0, [])
n_kumiawase = [k for k in kumiawase if total(k) >= g]
ans = n_kumiawase[0]
for k in n_kumiawase:
    if sum(k) < sum(ans):
        ans = k
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

def score(d, n, s, ans):
    if s >= G:
        ans = min(ans, n)
        return ans
    if d == D:
        if s >= G:
            ans = min(ans, n)
        return ans
    p, c = PC[d]
    for k in range(p+1):
        if k == p:
            ans = score(d+1, n+k, 100*(d+1)*k + c + s, ans)
        else:
            ans = score(d+1, n+k, 100*(d+1)*k + s, ans)
    return ans

print(score(0, 0, 0, 1000))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

def score(d, n, s, ans):
    if d == D:
        if s >= G:
            ans = min(ans, n)
        return ans
    p, c = PC[d]
    for k in range(p+1):
        if k == p:
            ans = score(d+1, n+k, 100*(d+1)*k + c + s, ans)
        else:
            ans = score(d+1, n+k, 100*(d+1)*k + s, ans)
    return ans

print(score(0, 0, 0, 1000))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

min_count = sum(x[0] for x in pc)

for comb in itertools.permutations(range(d)):
    count = 0
    rem_g = g
    for j in range(d):
        i = comb[j]
        comp = pc[i][0]*(i+1)*100 + pc[i][1]
        if rem_g <= comp:
            count += min(-(-rem_g//(100*(i+1))),pc[i][0])
            break
        else:
            count += pc[i][0]
            rem_g -= comp
    min_count = min(min_count,count)

print(min_count)

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

P     = [None] * D
C     = [None] * D
count = [None] * D
score = [None] * D

for i in range(D):
    p, c          = map(int, input().split())
    P[i]          = p
    C[i]          = c
    count[i]      = list(range(p+1))
    score[i]      = [100 * (i+1) * j for j in range(p+1)]
    score[i][-1] += c

answer = sum(P)

for is_complete in itertools.product([True, False], repeat=D):
    score_tmp  = 0
    count_tmp  = 0
    score_tmp += sum([score[i][-1] for i in range(D) if is_complete[i]])
    count_tmp += sum([count[i][-1] for i in range(D) if is_complete[i]])
    while score_tmp < G:
        for i in list(range(D))[::-1]:
            if is_complete[i] == False:
                if (G - score_tmp) % (100 * (i+1)) == 0:
                    count_add  = min((G - score_tmp) // (100 * (i+1)),     P[i] - 1)
                else:
                    count_add  = min((G - score_tmp) // (100 * (i+1)) + 1, P[i] - 1)
                score_add      = 100 * (i+1) * count_add
                count_tmp     += count_add
                score_tmp     += score_add
            if score_tmp >= G:
                break
    if score_tmp >= G:
        answer = min(answer, count_tmp)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

P     = [None] * D
C     = [None] * D
count = [None] * D
score = [None] * D

for i in range(D):
    p, c          = map(int, input().split())
    P[i]          = p
    C[i]          = c
    count[i]      = list(range(p+1))
    score[i]      = [100 * (i+1) * j for j in range(p+1)]
    score[i][-1] += c

count = [sum(c) for c in list(itertools.product(*count))]
score = [sum(s) for s in list(itertools.product(*score))]

answer = [count[i] for i in range(len(count)) if score[i] >= G]

print(min(answer))