問題一覧 > 通常問題

No.1541 ゅゅさんのテスト勉強

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : logxlogx / テスター : 57tggx57tggx ゅゅゅゅ とりゐとりゐ pepper_aobutapepper_aobuta
1 ProblemId : 6533 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-06 18:19:47

問題文

ゅゅさんの学校では,明日に期末テスト当日が迫っています.
テストは $N$ 科目もありますが,ゅゅさんはまだテスト勉強を始めていません.
ゅゅさんのテスト勉強とテストでの得点について,次が成り立ちます.なお,ゅゅさんの学校ではテストに満点が存在せず,各教科には $1$ から $N$ までの番号がついています.

  • $i=1,\dots,N$ について,教科 $i$ を勉強すると教科 $i$ で $M$ 点を取れるようになる.
  • 教科 $i$ を勉強すると, $k_i$ 個の教科 $A_{ij}\ (1\leq j \leq k_i)$ について深い理解を得やすくなる.
    これにより,教科 $i$ と $A_{ij}$ をどちらも勉強した時,教科 $A_{ij}$ の得点が $B_{ij}$ 点上がる.
  • テスト勉強は疲れるので,教科 $i$ を勉強したらもふもふ成分を $C_i$ だけ補充しないといけない.

さて,ゅゅさんはテストで良い成績を取りたいですが,もったいないのでもふもふ成分を補充しすぎたくありません.
適切に勉強する科目を選ぶことで, (テストでの得点の総和) $-$ (補充するもふもふ成分) の値を最大化してください.

入力

$N\ M$
$\mathrm{Info}_1$
$\vdots$
$\mathrm{Info}_N$

ただし,各 $\mathrm{Info}_i$ は次の形式で与えられる.なお, $k_i=0$ の時, $\mathrm{Info}_i$ は $1$ 行のみからなる.

$k_i\ C_i$
$A_{i1}\ \cdots\ A_{ik_{i}}$
$B_{i1}\ \cdots\ B_{ik_{i}}$

  • $1 \leq N \leq 100$
  • $0 \leq M \leq 10^9$
  • $0 \leq k_i \leq N-1\ (1 \leq i \leq N)$
  • $1 \leq A_{ij} \leq N,\ A_{ij} \neq i\ (1\leq i \leq N,\ 1 \leq j \leq k_i)$
  • $A_{ij} \lt A_{i(j+1)}\ (1\leq i \leq N,\ 1 \leq j \lt k_i)$
  • $0 \leq B_{ij},\,C_i \leq 10^9\ (1 \leq i \leq N,\,1 \leq j \leq k_i)$
  • 入力は全て整数

出力

ゅゅさんが適切に勉強する科目を選択した時に得られる,(テストでの得点の総和) $-$ (補充するもふもふ成分)の最大値を出力してください.

最後に改行してください.

サンプル

サンプル1
入力
3 100
1 50
2
15
1 200
3
5
2 20
1 2
20 10
出力
150

教科 $1,3$ を勉強するのが最適です.

サンプル2
入力
3 100
1 1000000000
2
15
1 1000000000
3
5
2 1000000000
1 2
20 10
出力
0

必要なもふもふ成分が多すぎるため,一科目も勉強をしないのが最適です.本当にテスト勉強をしなくて大丈夫なのでしょうか.

サンプル3
入力
3 0
0 5
0 5
0 5
出力
0

何をしてもテストで得点を得られません.よって,一科目も勉強をしないのが最適です.

サンプル4
入力
5 457570553
2 935681835
3 5
646317136 229179330
1 732053682
5
460010336
3 219961142
2 4 5
805316947 35611550 19086292
2 80909206
3 5
896187710 518478057
2 391491330
3 4
767870553 307252308
出力
4613065789

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。