items = {
    {"map", 9, 150},
    {"compass", 13, 35},
    {"water", 153, 200},
    {"sandwich", 50, 160},
    {"glucose", 15, 60},
    {"tin", 68, 45},
    {"banana", 27, 60},
    {"apple", 39,  40},
    {"cheese", 23, 30},
    {"beer", 52, 10},
    {"suntan cream", 11, 70},
    {"camera", 32, 30},
    {"t-shirt", 24, 15},
    {"trousers", 48, 10},
    {"umbrella", 73, 40},
    {"waterproof trousers", 42, 70},
    {"waterproof overclothes", 43, 75},
    {"note-case", 22, 80},
    {"sunglasses", 7, 20},
    {"towel", 18, 12},
    {"socks", 4, 50},
    {"book", 30, 10},
}

local unpack = table.unpack

function m(i, w)
    if i<1 or w==0 then
        return 0, {}
    else
        local _, wi, vi = unpack(items[i])
        if wi > w then
            return mm(i - 1, w)
        else
            local vn, ln = mm(i - 1, w)
            local vy, ly = mm(i - 1, w - wi)
            if vy + vi > vn then
                return vy + vi, { i, ly }
            else
                return vn, ln
            end
        end
    end
end

local memo, mm_calls = {}, 0
function mm(i, w)