Buggy python submission (verdict: Time Limit Exceeded):
#coding:utf-8

from collections import defaultdict
import itertools

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))

    items = defaultdict(list)
    item_num = defaultdict(int)
    for i in range(N):
        w, v = map(int, raw_input().split(" "))
        if i == 0:
            w_list = range(w, w + 4)
        items[w].append(v)
        item_num[w] += 1

    for k in items.keys():
        items[k].sort(reverse = True)

    cum = defaultdict(list)
    for k in items.keys():
        sum_val = 0
        for e in items[k]:
            sum_val += e
            cum[k].append(sum_val)

    max_val = 0
    weights = items.keys()
    kinds = len(items.keys())
    for element in itertools.product(range(N + 1), repeat = kinds):
        w_sum = 0
        over_flag = False
        for i in range(kinds):
            if element[i] > item_num[weights[i]]:
                over_flag = True
                break
            w_sum += weights[i] * element[i]

        if w_sum > W or over_flag:
            continue

        val = 0
        for i in range(kinds):
            if element[i] >= 1:
                val += cum[weights[i]][element[i] - 1]
        if val > max_val:
            max_val = val

    print max_val


Fixed submission:
#coding:utf-8

N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)

Buggy python submission (verdict: Time Limit Exceeded):
#coding:utf-8

from collections import defaultdict
import itertools

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))

    items = defaultdict(list)
    item_num = defaultdict(int)
    for i in range(N):
        w, v = map(int, raw_input().split(" "))
        if i == 0:
            w_list = range(w, w + 4)
        items[w].append(v)
        item_num[w] += 1

    for k in items.keys():
        items[k].sort(reverse = True)

    max_val = 0
    weights = items.keys()
    kinds = len(items.keys())
    for element in itertools.product(range(N + 1), repeat = kinds):
        w_sum = 0
        for i in range(kinds):
            w_sum += weights[i] * element[i]
        if w_sum > W:
            continue
        val = 0
        for i in range(kinds):
            val += sum(items[weights[i]][:element[i]])
        if val > max_val:
            max_val = val

    print max_val


Fixed submission:
#coding:utf-8

N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)

Buggy python submission (verdict: Runtime Error):
#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]


Fixed submission:
#coding:utf-8

N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)