def Advisor0 (subjects, maxWork, i, bestSubset, bestSubsetValue,
                            subset, subsetValue, subsetWork):
    m = {}
    return dpAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
                            subset, subsetValue, subsetWork, m)

def dpAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue,
                            subset, subsetValue, subsetWork, m):
    # Hit the end of the list.
    if (i,subsetValue,subsetWork) in m:
        return m[(i,subsetValue,subsetWork)]
    else:
        if i >= len(subjects):
            if bestSubset == None or subsetValue > bestSubsetValue:
                m[(i,subsetValue,subsetWork)] = subset[:], subsetValue
                return subset[:], subsetValue
            else:
                # Keep the current best.
                m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
                return bestSubset, bestSubsetValue
        else:
            s = subjects[i]
            # Try including subjects[i] in the current working subset.
            if subsetWork + s[WORK] <= maxWork:
                subset.append(i)
                bestSubset, bestSubsetValue = dpAdvisorHelper(subjects,
                        maxWork, i+1, bestSubset, bestSubsetValue, subset,
                        subsetValue + s[VALUE], subsetWork + s[WORK],m)
                m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
                subset.pop()
            bestSubset, bestSubsetValue = dpAdvisorHelper(subjects,
                    maxWork, i+1, bestSubset, bestSubsetValue, subset,
                    subsetValue, subsetWork, m)
            m[(i,subsetValue,subsetWork)] = bestSubset, bestSubsetValue
        return bestSubset, bestSubsetValue

def dpAdvisor(subjects, maxWork):
    """
    Returns a dictionary mapping subject name to (value, work) that contains a
    set of subjects that provides the maximum value without exceeding maxWork.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    returns: dictionary mapping subject name to (value, work)
    """
    nameList = subjects.keys()
    tupleList = subjects.values()
    bestSubset, bestSubsetValue = \
            Advisor0(tupleList, maxWork, 0, None, None, [], 0, 0)
    outputSubjects = {}
    print bestSubset, bestSubsetValue
    for i in bestSubset:
        outputSubjects[nameList[i]] = tupleList[i]
    return outputSubjects