题目内容

云实例加固需要配齐 $n$ 个安全组件，每个组件都必须恰好选择一种型号。第 $i$ 个组件有 $m_i$ 种型号，第 $j$ 种的部署成本为 $a_{i,j}$，防护收益为 $v_{i,j}$。总成本不能超过预算 $x$。

请计算在买齐全部组件的前提下，防护收益之和的最大值。如果无论如何都买不齐，输出 -1。

约束：$1 \le n,m_i \le 4 \times 10^{1}$，$1 \le a_{i,j}, v_{i,j}, x \le 1000000000$，且所有 $m_i$ 之和不超过 $4 \times 10^{1}$。

输入描述

第一行包含两个正整数 $n$ 和 $x$，分别表示组件个数与预算。