比赛已经结束。新提交将被视为补题提交，不计入比赛成绩。

题目背景

史蒂夫到达地狱交通时打开了存放物资的箱子想拿些东西，但箱子里的物品太多了，他想让你帮忙规划一下。

题目描述

箱子里有 $n$ 格物品，每格物品可能是黑曜石（用 1 表示）、钻石（用 2 表示）或其他物品（用 3 表示）。每格物品有数量 $w_i$ 和单位价值 $v_i$，他的背包最大容纳物品数量为 $W$。不在同一格的同一类物品，其数量和单位价值也可能不同。

史蒂夫的想法是：

1. 黑曜石全部带走。
2. 钻石可以选择带走，如果带走，需满足带走的数量是质数。
3. 其他物品可以选择带走，如果带走，总价值需满足 $v_i\equiv1\pmod3$。
4. 每次操作都只能一次带走一整格（装不下就不能带走）。

背包并不要求装满。

请你求出在满足史蒂夫想法情况下可带走物品的最大价值。

输入格式

第一行两个整数 $n,W$。

接下来 $n$ 行，每行三个整数 $t_i,w_i,v_i$，表示物品 $i$ 的类型、数量、单位价值。

输出格式

满足史蒂夫想法情况下可带走物品的最大价值。

输入输出样例

3 75
1 16 8
2 64 512
3 9 128

30336

说明 / 提示

【样例解释】

带走 $16$ 个黑曜石和 $59$ 个钻石，满足条件，总价值为 $16\times8+59\times512=30336$。

【数据范围与约定】

对于 $100\%$ 的数据，$1\le n\le1000,1\le W\le2^{15},t_i\in\{1,2,3\},1\le w_i\le2^7,1\le v_i\le2^{10}$。

保证背包的空间可以支持将黑曜石全部带走。