Problem:


Score : 400 points

Problem Statement

You have N items and a bag of strength W.
The i-th item has a weight of w_i and a value of v_i.

You will select some of the items and put them in the bag.
Here, the total weight of the selected items needs to be at most W.

Your objective is to maximize the total value of the selected items.

Constraints

1 ≤ N ≤ 100

1 ≤ W ≤ 10^9

1 ≤ w_i ≤ 10^9

For each i = 2,3,...,N, w_1 ≤ w_i ≤ w_1 + 3.

1 ≤ v_i ≤ 10^7

W, each w_i and v_i are integers.

Input

Input is given from Standard Input in the following format:

N W
w_1 v_1
w_2 v_2
:
w_N v_N

Output

Print the maximum possible total value of the selected items.

Sample Input 1

4 6
2 1
3 4
4 10
3 4

Sample Output 1

11

The first and third items should be selected.

Sample Input 2

4 6
2 1
3 7
4 10
3 6

Sample Output 2

13

The second and fourth items should be selected.

Sample Input 3

4 10
1 100
1 100
1 100
1 100

Sample Output 3

400

You can take everything.

Sample Input 4

4 1
10 100
10 100
10 100
10 100

Sample Output 4

0

You can take nothing.



Sample input:
4 6
2 1
3 4
4 10
3 4


Sample output:
11

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
import sys

"""
recursionlimit増やす
"""
sys.setrecursionlimit(1000000)
def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    return F[n-1][limit]

def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    i=limit

    return F[n-1][limit],i

if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    N,W =map(int,input().split()) 
    vs=[]
    ws=[]
    for i in range(N):
        tmpv,tmpw=map(int,input().split())
        ws.append(tmpv)
        vs.append(tmpw)
    print(knapsack(vs,ws,W,N)[0])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
import sys

"""
recursionlimit増やす
"""
sys.setrecursionlimit(1000000)
def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    return F[n-1][limit]

def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    i=limit
    while True:
        if F[n-1][i]!=F[n-1][i-1]:
            break
        i-=1
    return F[n-1][limit],i

if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    N,W =map(int,input().split()) 
    vs=[]
    ws=[]
    for i in range(N):
        tmpv,tmpw=map(int,input().split())
        ws.append(tmpv)
        vs.append(tmpw)
    print(knapsack(vs,ws,W,N)[0])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    return F[n-1][limit]

def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    i=limit
    while True:
        if F[n-1][i]!=F[n-1][i-1]:
            break
        i-=1
    return F[n-1][limit],i

if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    N,W =map(int,input().split()) 
    vs=[]
    ws=[]
    for i in range(N):
        tmpv,tmpw=map(int,input().split())
        ws.append(tmpv)
        vs.append(tmpw)
    print(knapsack(vs,ws,W,N)[0],sep="\n")

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Here your code !
def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    return F[n-1][limit]

def knapsack(v, w, limit, n):
    """straightforward DP solution

    Arguments:
    - `v`: list of values
    - `w`: list of weights
    - `limit`: maximum limit
    - `n`: number of items
    """ 
    F = [[0] * (limit + 1) for x in range(n + 1)] 
    for i in range(0, n):                # F[-1] is all 0.
        for j in range(limit + 1):
            if j >= w[i]:
                F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i])
            else:
                F[i][j] = F[i - 1][j]
    i=limit
    while True:
        if F[n-1][i]!=F[n-1][i-1]:
            break
        i-=1
    return F[n-1][limit],i

if __name__ == '__main__':
    # ??????????????\???
    # limit = 50
    # data = [[60, 10], [100, 20], [120, 30], [210, 45], [10, 4]]
    case_no = 1
    while True:
        W = int(input())
        if W == 0:
            break
        print("Case "+str(case_no)+":")
        N = int(input())
        vs=[]
        ws=[]
        for i in range(N):
            tmpv,tmpw=map(int,input().split(","))
            vs.append(tmpv)
            ws.append(tmpw)
        print(*knapsack(vs,ws,W,N),sep="\n")
        case_no+=1

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())
dp = [[None] * (W+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W):#dp[i]:
        if dp[i][j] == None:
            continue
        if j + w <= W:
            dp[i+1][j+w] = max(dp[i][j] + v, dp[i][j+w] or 0)
        dp[i+1][j] = dp[i][j]
print(max([i for i in dp[N] if i != None]))

Submission status: Runtime Error

Solution code:
#Simple Knapsack

N,W = list(map(int, input().split()))

w = []
v = []
for i in range(N):
    wi,vi = list(map(int, input().split()))
    w.append(wi)
    v.append(vi)

#メモ化再帰
dp = [[-1]*(W+1) for i in range(N+1)]
def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else: 
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) 
        dp[i][j] = res 
    return res 
print(rec(0, W))

Submission status: Runtime Error

Solution code:
N, W = list(map(int, input().split()))
w_list = list()
v_list = list()

for _ in range(N):
    w, v = list(map(int, input().split()))
    w_list.append(w)
    v_list.append(v)

cases = [[0]*(W+1)]

for i_item in range(1, N+1):
    case = [0]
    w = w_list[i_item-1]
    v = v_list[i_item-1]
    for i_w in range(1, W+1):
        if w > i_w:
            val = cases[i_item-1][i_w]
        else:
            val = max(cases[i_item-1][i_w], cases[i_item-1][i_w-w] + v)
        case.append(val)
    cases.append(case)

print(cases[N][W])

Submission status: Runtime Error

Solution code:
import copy
N, W = [int(i) for i in input().split(' ')]
dic = {}

for i in range(N):
    new_w, new_v = [int(i) for i in input().split(' ')]
    if new_w in dic:
        dic[new_w].append(new_v)
    else:
        dic[new_w] = [new_v]
for key in dic.keys():
    dic[new_w].sort(reverse=True)
w = list(dic.keys())

def rec(i, j, _dic):
    if w[i]>j:
        return 0
    cand = []
    if len(_dic[w[i]])>=1:
        new_dic = copy.deepcopy(_dic)
        val = new_dic[w[i]].pop(0)
        cand.append(val+rec(i, j-w[i], new_dic))
    if i+1<len(w):
        cand.append(rec(i+1,j, _dic))
    return max(cand)

print(rec(0, W, dic))

Submission status: Runtime Error

Solution code:

# input
NW = [int(x) for x in input().split(" ")]
N = NW[0]
W = NW[1]

w = []
v = []

for _ in range(N):
	wv = [int(x) for x in input().split(" ")]
	w.append(wv[0])
	v.append(wv[1])

memo = [[-1 for _ in range(N)] for _ in range(W+1)]

print(memo)
# 品物i-Nまでを使って容量Wのナップサックにいれられる品物の価値の総和の最大値
def rec(i, Wrec):
	if i >= N:
		return 0
	if memo[Wrec][i] != -1:
		"use memo"
		return memo[Wres][i]

	a = -1
	if Wrec - w[i] >= 0:
		a = v[i]+rec(i+1, Wrec-w[i])
	b = rec(i+1, Wrec)

	ret =  max(a, b)
	memo[Wrec][i] = ret
	return ret

print(rec(0,W))

Submission status: Runtime Error

Solution code:
# ARC60 D recursive with memorization
dp = [{} for j in range(N+1)]
def rec_dp(i, j):
    if(j in dp[i]):
        return dp[i][j]
    
    res = 0
    if(i == N):
        res = 0
    elif(j < w[i]):
        res = rec_dp(i+1, j)
    else:
        res = max(rec_dp(i+1, j), rec_dp(i+1, j-w[i]) + v[i])
    
    dp[i][j] = res
    return res

print(rec_dp(0, w_limit))

Submission status: Runtime Error

Solution code:

N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
w.insert(0,"0")
v.insert(0,"0")
for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]






Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Runtime Error

Solution code:

N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

w.insert(0,"0")
v.insert(0,"0")




Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Runtime Error

Solution code:


N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w,v = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

w.insert(0,"0")
v.insert(0,"0")




Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[i]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w,v = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

w.insert(0,"0")
v.insert(0,"0")




Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[1]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Runtime Error

Solution code:

N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w,v = map(int,input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

w.insert(0,"0")
v.insert(0,"0")




Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[1]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Runtime Error

Solution code:
N,W = map(int, input().split())


w=[0 for i in range(N)]
v=[0 for i in range(N)]

Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w,v = map(int,input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]






Wmin = min(w)

nap_memo ={}

def nap(i,W2):
    kagi = str(i) + ':' +str(W2)
    if kagi in nap_memo:
        return nap_memo[kagi]
    elif i ==0:
        r=0
    elif W2<Wmin:
        r=0
    elif W2 < Wmin:
        r=0
    elif W2 < w[i]:
        r=nap(i-1,W2)
    elif Wsum[i]<=W2:
        r=Vsum[1]
    else:
        r=max( nap(i-1,W2-w[i])+v[i],nap(i-1,W2))
        
    nap_memo[kagi]=r
    return r

print(nap(N,W))

Submission status: Runtime Error

Solution code:
n, w = map(int, input().split())
w_d = {}
w_l = []
for _ in range(3):
    w_i, v_i = map(int, input().split())
    w_l.append(w_i)
    w_d[w_i] = [v_i]
for i in range(3, n):
    w_i, v_i = map(int, input().split())
    w_d[w_i].append(v_i)
for i in range(3):
    w_d[w_l[i]] = sorted(w_d[w_l[i]], reverse=True)

m = 0
for i_0 in range(len(w_d[w_l[0]]) + 1):
    for i_1 in range(len(w_d[w_l[1]]) + 1):
        for i_2 in range(len(w_d[w_l[2]]) + 1):
            for i_3 in range(len(w_d[w_l[3]]) + 1):
                sum_w = w_l[0] * i_0 + w_l[1] * \
                    i_1 + w_l[2] * i_2 + w_l[3] * i_3
                if sum_w > w:
                    continue
                sum_v = sum(w_d[w_l[0]][:i_0]) + sum(w_d[w_l[1]][:i_1]) + \
                    sum(w_d[w_l[2]][:i_2]) + sum(w_d[w_l[3]][:i_3])
                m = max(m, sum_v)
print(m)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	ll ans = 0LL;
	int N, W;
	cin >> N >> W;
	vl w(N), v(N);
	rep(i, N) cin >> w[i] >> v[i];
	deque<ll> V[4];
	rep(i, N) V[w[i]-w[0]].push_back(v[i]);
	rep(i, 4) sort(rall(V[i]));
	rep(i, 4) REP(j, 1, V[i].size()) V[i][j] += V[i][j-1];
	rep(i, 4) V[i].push_front(0LL);
	rep(i, V[0].size()) rep(j, V[1].size()) rep(k, V[2].size()) rep(l, V[3].size()) {
		ll now_W = 0LL;
		now_W += (ll)w[0]*(i);
		now_W += (ll)(w[0]+1)*(j);
		now_W += (ll)(w[0]+2)*(k);
		now_W += (ll)(w[0]+3)*(l);
		//cout << " i: " << i << " j: " << j <<" k: " << k << " l: " << l << " w: " << now_W << " v: " << V[0][i] + V[1][j] + V[2][k] + V[3][l] <<endl;
		if(now_W <= W) ans = max(ans, V[0][i] + V[1][j] + V[2][k] + V[3][l]);
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:

N,W = map(int, input().split())

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

#品物、重み→1〜N番目
for i in range(N):
    w[i+1],v[i+1] = map(int, input().split())

for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときは価値は0
    if i == 0:
        return 0
    #制約0のときも価値は0
    if W == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    if Wsum[i] <= W2:
        return Vsum[i]
        
    #i番目の品物をナップサックに入れるか入れないか
    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W), flush = True))

Submission status: Runtime Error

Solution code:
#coding:utf-8

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))
    item = []
    for i in range(N):
        item.append(map(int, raw_input().split(" ")))

    table = [[0 for j in range(W + 1)] for i in range(N)]

    for i in range(N):
        for j in range(W + 1):
            if item[i][0] <= j:
                table[i][j] = max(table[i - 1][j], table[i - 1][j - item[i][0]] + item[i][1])
            else:
                table[i][j] = table[i - 1][j]

    print table[N - 1][W]

Submission status: Runtime Error

Solution code:
# coding: utf-8

if __name__ == "__main__":
	n, w = map(int,input().split())
	v, w = [], []

	for i in range(n):
		w_, v_ = map(int,input().split())
		w.append(w_)
		v.append(v_)

	nap_memo = {}
	def nap(i,j):
		key = str(i)+':'+str(j)

		if key in nap_memo:
			return nap_memo[key]

		r = 0
		if i == n:
			r = 0
		elif j < w[i]:
			r = nap(i+1,j)
		else:
			r = max(nap(i+1, j),
					nap(i+1, j-w[i]) + v[i])

		nap_memo[key] = r
		return r

	print(nap(0,w))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import numpy as np

N, MaxTotalWeight = map(int, raw_input().split())

def getWeightValuePair(W,Values,WeightValuePair):
    totalValue = 0
    WeightKeys = WeightValuePair.keys()
    WeightValuePairCopy = WeightValuePair.copy()
    for i in xrange(len(Values)):
        totalValue += Values[i]
        for totalWeight in WeightKeys:
            if (totalWeight + W * (i+1)) <= MaxTotalWeight:
                if (totalWeight + W * (i+1)) not in WeightValuePair:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
                elif WeightValuePairCopy[totalWeight] +  totalValue > WeightValuePairCopy[totalWeight + W * (i+1)]:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
    return WeightValuePair

Weights = []
WeightsValues = []

for i in xrange(N):
    tempData = map(int, raw_input().split())        
    if i == 0:
        Weights.append(tempData[0])
        Weights.append(tempData[0]+1)
        Weights.append(tempData[0]+2)
        Weights.append(tempData[0]+3)
        WeightsValues.append([tempData[1]])
        WeightsValues.append([])
        WeightsValues.append([])
        WeightsValues.append([])
    else:
        WeightsValues[tempData[0] - Weights[0]].append(tempData[1])

for data in WeightsValues:
    data.sort(reverse=True)

returnWeightValuePair = {0:0}
for i in range(4):
    returnWeightValuePair = getWeightValuePair(Weights[i],WeightsValues[i],returnWeightValuePair)

print max(returnWeightValuePair.values())

Submission status: Runtime Error

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力

N, MaxTotalWeight = map(int, raw_input().split())

def getWeightValuePair(W,Values,WeightValuePair):
    totalValue = 0
    WeightKeys = WeightValuePair.keys()
    WeightValuePairCopy = WeightValuePair.copy()
    for i in range(len(Values)):
        totalValue += Values[i]
        for totalWeight in WeightKeys:
            if (totalWeight + W * (i+1)) <= MaxTotalWeight:
                if (totalWeight + W * (i+1)) not in WeightValuePair:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
                elif WeightValuePairCopy[totalWeight] +  totalValue > WeightValuePairCopy[totalWeight + W * (i+1)]:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
    return WeightValuePair

Weights = []
WeightsValues = []

for i in xrange(N):
    tempData = map(int, raw_input().split())        
    if i == 0:
        Weights.append(tempData[0])
        Weights.append(tempData[0]+1)
        Weights.append(tempData[0]+2)
        Weights.append(tempData[0]+3)
        WeightsValues.append([tempData[1]])
        WeightsValues.append([])
        WeightsValues.append([])
        WeightsValues.append([])
    else:
        WeightsValues[tempData[0] - Weights[0]].append(tempData[1])

for data in WeightsValues:
    data.sort(reverse=True)

returnWeightValuePair = {0:0}
for i in range(4):
    returnWeightValuePair = getWeightValuePair(Weights[i],WeightsValues[i],returnWeightValuePair)

print long(max(returnWeightValuePair.values()))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import numpy as np

N, MaxTotalWeight = map(int, raw_input().split())

def getWeightValuePair(W,Values,WeightValuePair):
    totalValue = 0
    WeightKeys = WeightValuePair.keys()
    WeightValuePairCopy = WeightValuePair.copy()
    for i in range(len(Values)):
        totalValue += Values[i]
        for totalWeight in WeightKeys:
            if (totalWeight + W * (i+1)) <= MaxTotalWeight:
                if (totalWeight + W * (i+1)) not in WeightValuePair:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
                elif WeightValuePairCopy[totalWeight] +  totalValue > WeightValuePairCopy[totalWeight + W * (i+1)]:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
    return WeightValuePair

Weights = []
WeightsValues = []

for i in xrange(N):
    tempData = map(int, raw_input().split())        
    if i == 0:
        Weights.append(tempData[0])
        Weights.append(tempData[0]+1)
        Weights.append(tempData[0]+2)
        Weights.append(tempData[0]+3)
        WeightsValues.append([tempData[1]])
        WeightsValues.append([])
        WeightsValues.append([])
        WeightsValues.append([])
    else:
        WeightsValues[tempData[0] - Weights[0]].append(tempData[1])

for data in WeightsValues:
    data.sort(reverse=True)

returnWeightValuePair = {0:0}
for i in range(4):
    returnWeightValuePair = getWeightValuePair(Weights[i],WeightsValues[i],returnWeightValuePair)

print long(max(returnWeightValuePair.values()))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# 整数の入力
#a = int(raw_input())
# スペース区切りの整数の入力
import numpy as np

N, MaxTotalWeight = map(int, raw_input().split())

def getWeightValuePair(W,Values,WeightValuePair):
    totalValue = 0
    WeightKeys = WeightValuePair.keys()
    WeightValuePairCopy = WeightValuePair.copy()
    for i in range(len(Values)):
        totalValue += Values[i]
        for totalWeight in WeightKeys:
            if (totalWeight + W * (i+1)) <= MaxTotalWeight:
                if (totalWeight + W * (i+1)) not in WeightValuePair:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
                elif WeightValuePairCopy[totalWeight] +  totalValue > WeightValuePairCopy[totalWeight + W * (i+1)]:
                    WeightValuePair[totalWeight + W * (i+1)] = WeightValuePairCopy[totalWeight] +  totalValue
    return WeightValuePair

Weights = []
WeightsValues = []

for i in xrange(N):
    tempData = map(int, raw_input().split())        
    if i == 0:
        Weights.append(tempData[0])
        Weights.append(tempData[0]+1)
        Weights.append(tempData[0]+2)
        Weights.append(tempData[0]+3)
        WeightsValues.append([tempData[1]])
        WeightsValues.append([])
        WeightsValues.append([])
        WeightsValues.append([])
    else:
        WeightsValues[tempData[0] - Weights[0]].append(tempData[1])

for data in WeightsValues:
    data.sort(reverse=True)
    print data

returnWeightValuePair = {0:0}
for i in range(4):
    returnWeightValuePair = getWeightValuePair(Weights[i],WeightsValues[i],returnWeightValuePair)

print long(max(returnWeightValuePair.values()))

Submission status: Runtime Error

Solution code:
n, l = map(int, raw_input().split())
dp = [-1 for j in range(10000)]

for i in range(n):
	w, v = map(int, raw_input().split())
	for j in reversed(range(ma)):
		if dp[j] != -1:
			dp[min(ma, j + w)] = max(dp[min(ma, j + w)], dp[j] + v)
	dp[w] = v

dp[0] = 0

for i in reversed(range(l + 1)):
	if dp[i] != -1:
		print dp[i]
		break

Submission status: Runtime Error

Solution code:
n, l = map(int, raw_input().split())
ma = l * 200 + 5
dp = [-1 for j in range(ma)]

for i in range(n):
	w, v = map(int, raw_input().split())
	for j in reversed(range(ma)):
		if dp[j] != -1:
			dp[min(ma, j + w)] = max(dp[min(ma, j + w)], dp[j] + v)
	dp[w] = v

dp[0] = 0

for i in reversed(range(l + 1)):
	if dp[i] != -1:
		print dp[i]
		break

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n,weight = map(int, raw_input().split())

v = [0]*n
w = [0]*n
    
for i in range(n):
    w[i],v[i] = map(int, raw_input().split())

dp = [[0]*(weight+1)]*(n+1)

for i in range(n):
    for j in range(weight+1):
        if (j < w[i]):
          dp[i+1][j] = dp[i][j];
        else:
          dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);

print(dp[n][weight])

Submission status: Runtime Error

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(x[0] - w1 + 40)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000000:
	print(f1())
else:
	print(f2())

Submission status: Runtime Error

Solution code:
def f1():
	L.sort(key = (lambda x: - x[1]//(w1 - x[0] + 1)))
	ans = 0
	w2 = 0
	i = 0
	while i < N:
		w2 = w2 + L[i][0]
		if w2 > W:
			break
		ans = ans + L[i][1]
		i = i + 1
	
	return ans

def f2():
	dp = [[0] * (W + 1) for i in range(N + 1)]
	for n in range(1,N + 1):
		w,v = L[n - 1]
		if w > W:
			continue
		for m in range(w):
			dp[n][m] = dp[n - 1][m]
		for m in range(w,W + 1):
			dp[n][m] = max(dp[n - 1][m - w] + v, dp[n - 1][m])
	return max(dp[-1])
	
N,W = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]
w1 = L[0][0]
if w1 > 10000:
	print(f1())
else:
	print(f2())

Submission status: Runtime Error

Solution code:
import numpy as np
N, W = map(int, input().split())

w = np.array([])
v = np.array([])

for i in range(N):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

from functools import lru_cache

@lru_cache(maxsize = 10000)
def d(i, j):
    if i == 0:
        if w[0] <= j:
            return v[0]
        else:
            return 0
    else:
        if j >= w[i]:
            return max(d(i-1, j), d(i-1, j-w[i]) + v[i])
        else:
            return d(i-1, j)

print(d(N - 1, W))

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, input().split())
lw = [0]
lv = [0]
for i in range(N):
    w, v = map(int, input().split())
    lw.append(w)
    lv.append(v)

ar = np.array([0] * (N+1) * (W+1)).reshape(N+1,W+1)

for i in range(1,N+1):
    for w in range(1,W+1):
        if lw[i] <= w:
            if lv[i] + ar[i-1, w- lw[i]] > ar[i-1, w]:
                ar[i,w] = lv[i] + ar[i-1, w - lw[i]]

            else:
                ar[i, w] = ar[i-1,w]

        else:
            ar[i,w] = ar[i-1,w]

print(np.max(ar))

Submission status: Runtime Error

Solution code:
def d():
    n, w = map(int, input().split())
    shop = []
    for i in range(n):
        shop.append( list(map(int, input().split())) )
    # s = sorted(shop, key= lambda item: item[1]/item[0], reverse=True)
    # print(n, w, s)
    best = 0
    k = n-2
    while k <= n:
        bag = [0, 0]
        i = 0
        while i < k:
            item = s[i]
            i += 1
            if bag[0]+item[0] <= w:
                bag[0] += item[0]
                bag[1] += item[1]
            else:
                continue
        best = max(best, bag[1])
        k += 1
    print(best)

d()

Submission status: Runtime Error

Solution code:
import numpy as np

N, W = map(int, raw_input().split())
w = np.array([])
v = np.array([])
for i in range(N):
    temp0, temp1 = map(int, raw_input().split())
    w = np.append(w, temp0)
    v = np.append(v, temp1)

table = np.array([])

def searchTable(item, weight):
    for i in range(len(table)):
        if table[i][0] == item and table[i][1] == weight:
            return True, table[i][2]
    return False, -1

def function(item, weight):
    flag, data = searchTable(item, weight)
    if flag:
        return data
    if item == N:
        result = 0
    elif weight < w[item]:
        result = function(item + 1, weight)
    else:
        result = max(function(item + 1, weight - w[item]) + v[item], function(item + 1, weight))
    table = np.append(table, np.array([item, weight, result]))
    return result

print(function(0, W))