def kns(weights, values, w):
    dic = [(weights[i], values[i]) for i in range(len(weights))]
    ks_wv = [0 for i in range(w+1)]

    for d in dic:
        weight = d[0]
        value = d[1]
        for _w in reversed(range(len(ks_wv))):
            # print("weight {}, w {}".format(weight, _w))
            if weight <= _w:
                ks_wv[_w] = max(ks_wv[_w], value + ks_wv[_w - weight])

    return ks_wv[w]

values = [60, 100, 120]
weights = [10, 20,  30]
values2 = [30, 15, 20, 20]
weights2 = [4, 1, 3, 1]
values3 = [7, 8, 6]
weights3 = [10, 9, 5]
values4 = [2, 10, 7, 3, 1, 12]
weights4 = [10, 29, 5, 5, 5, 24]
w = 50
w2 = 4
w3 = 15
w4 = 25

# print(kns(weights, values, w)) #220
# print(kns(weights2, values2, w2)) #40
# print(kns(weights3, values3, w3)) #14
print(kns(weights4, values4, w4)) #13