MAX_N = 100
MAX_W = 10000

knap = [
    {'weight':2, 'value':3},
    {'weight':1, 'value':2},
    {'weight':3, 'value':4},
    {'weight':2, 'value':2}
    ]

def main():
    W, N = 5, 4
    dp = [[0 for _ in range(MAX_W)] for _ in range(MAX_N)]

    for i in range(N):
        for j in range(W+1):
            if j < knap[i]['weight']:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j-knap[i]['weight']]+knap[i]['value'])
    print dp[N][W]

if __name__ == '__main__':
    main()