本番２時間デバッグしてバグが取れなかった問題。 http://tdpc.contest.atcoder.jp/tasks/tdpc_iwi

ここからは本番に解ききれず解説や他人のソースを参考に回答。 http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack