CF500F New Year Shopping

有 $n$ 种商品，第 $i$ 种商品的价格是 $c_i$ ，购买后可以增加 $h_i$ 的快乐指数，将于第 $t_i$ 天上市。商品的保质期为 $p$ 天，过期后不能再购买，即第 $i$ 种商品只能在第 $t_i$ 天到第 $t_i+p-1$ 天之间购买，每种商品只能购买一次。 有 $q$ 个询问，每次给定两个整数 $a,b$ ，求在第 $a$ 天去购物，最多使用 $b$ 元的情况下可以得到的最大快乐指数。询问之间互不干扰。

无

无

$1\le n\le 4\times 10^3, 1\le p \le 10^4$ $1\le c_i,h_i \le 4\times 10^3, 1\le t_i \le 10^4$ $1\le q \le 2\times 10^4,1\le a \le 2\times 10^4, 1\le b \le 4\times 10^3$