各商品を購入するかしないかを \(2^N\) 通り全て試し、その中で合計が \(M\) 以下となる中で得られる満足度の最大値を計算すれば良いです。

実装例(Python3)

n, m = map(int, input().split())
t = [-1] * n
p = [-1] * n
for i in range(n):
    t[i], p[i] = map(int, input().split())
ans = 0
for bi in range(1 << n):
    res_t, res_p = 0, 0
    for i in range(n):
        if (bi >> i) & 1:
            res_t += t[i]
            res_p += p[i]
    if res_t <= m:
        ans = max(ans, res_p)
print(ans)