解答①：Submission #16192313 - AtCoder Regular Contest 027
解法①：スペシャルチケットがx枚であるときは、x種類までしか品物を選ぶことができない。逆に、x種類までで品物を選ぶとしたらその中では通常のチケットとスペシャルチケットの枚数を区別する必要がない。
よって、dp[i][j][k] ：i番目の品物までで、j個品物を買っており(j ≦ x)、残りのチケット枚数がk枚であるときの嬉しさの最大値 としてDPする。
解答②：Submission #10481643 - AtCoder Regular Contest 027
解法②：今の品物の番目、残りのスペシャルチケットの枚数、残りの通常チケットの枚数を保持しながらメモ化再帰。
遷移は愚直にやるとスペシャルチケットi枚と通常チケットt[j] - i枚の使用を1 ≦ i ≦ t[j]で考えることになるが、これだとTLE。
「基本的にスペシャルチケットは1枚ずつ使用し、通常チケットを全部使うときに足りないチケットをスペシャルチケットで補う」みたいな考え方で遷移させるとうまくいった。
メモ化再帰のmemo用mapのキーをtupleにしていたらTLEだった。intにして3変数をうまく表現させるとぎりぎり間に合った。
