cp2.3

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 14 13:01:18 2014

@author: Administrator
"""

# 2.3.1
def bag01(n, w, v, W):
    d = [[0] * (W+1) for _ in xrange(n+1)]
    for i in xrange(1, n+1):
        for j in xrange(W+1):
            if j >= w[i-1]:
                d[i][j] = max(d[i-1][j], d[i-1][j-w[i-1]] + v[i-1])
            else:
                d[i][j] = d[i-1][j]
    return d[-1][-1]
    
def lcs(n, m, s, t):
    d = [[0] * (n+1) for _ in xrange(m + 1)]
    for i in xrange(1,n+1):
        for j in xrange(1, m+1):
            if s[i-1] == t[j-1]:
                d[i][j] = d[i-1][j-1] + 1
            else:
                d[i][j] = max(d[i-1][i], d[i][j-1])
    return d[-1][-1]
    
def fullbag(n, w, v, W):
    d = [[0] * (W+1) for _ in xrange(n+1)]
    for i in xrange(1, n+1):
        for j in xrange(W+1):
            for k in xrange(j / w[i-1] + 1):
                d[i][j] = max(d[i][j], d[i-1][j-k*w[i-1]] + k*v[i-1])
    return d[-1][-1]
    
def partsum(n, a, m, K):
    d = [[False] * (K+1) for _ in xrange(n+1)]
    d[0][0] = True
    for i in xrange(1, n+1):
        for j in xrange(K+1):
            for k in xrange(min(j/a[i-1], m[i-1]) + 1):
                d[i][j] |= d[i-1][j-k*a[i-1]]
    return d[-1][-1]
    
def lis(n, a):
    d = [1] * n
    for i in xrange(n):
        for j in xrange(i):
            if a[i] > a[j]:
                d[i] = max(d[i], d[j] + 1)
    return max(d)
    
def multcomb(n, m, a, M):
    d = [[0] * (m+1) for _ in xrange(n+1)]
    d[0][0] = 1
    for i in xrange(1, n+1):
        for j in xrange(m+1):
            for k in xrange(min(j, a[i-1]) + 1):
                d[i][j] += d[i-1][j-k]
    return d[-1][-1] % M