問題一覧 > 通常問題

No.783 門松計画

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 81
作問者 : maimai / テスター : はむこはむこ
4 ProblemId : 1784 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-10-12 11:36:35

定義

3つの要素から成る数列$v = (a_1,a_2,a_3)$が次の条件を満たす時,$v$は門松列であると言い伝えられています.

  1. $a_1,a_2,a_3$は全て異なる
  2. 3つの要素のうち$a_2$が最も大きい,あるいは最も小さい

さらに,$n$個の要素(ただし$3\le n$)から成る数列$w = (a_1,...,a_n)$が
どの連続した3つの要素を取り出しても門松列であるとき $w$は門松列列であると言います.

問題文

ユキコダホームセンターでは $N$ 種類の竹が売られています.
$i$ 本目の竹は長さ $L_i$ メートルで,価格は $W_i$ 円です.
どの竹も在庫は豊富にあるので,財布の許す限り何個でも買うことができます.

雪古寺さんは,幾つかの竹を購入して,竹の長さが門松列列になるように1列に並べたい.
竹は余らせたり切ったり繋げたり伸ばしたりしないものとします.

所持金 $C$ 円の制約の元で,門松列列の竹の長さの総和を最大化したとき,
作ることが出来る門松列列の竹の長さの総和を求めてください.
所持金を使い切る必要はありません.

入力

$N$ $C$
$L_1$ $\ldots$ $L_N$
$W_1$ $\ldots$ $W_N$

$1 \le N \le 50$
$1 \le C \le 50$
$1 \le L_i \le 50$
$1 \le W_i \le 50$
全て整数である.

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

出力

問題文の制約を満たす門松列列の竹の長さの総和を出力してください.
1つも作れない場合は0を出力します.

サンプル

サンプル1
入力
4 10
9 4 3 2
5 3 1 3
出力
17

9[m]5円の竹を2つ買うと,長さの総和を最大に出来ますが,門松列列を構成できません.

9[m]5円を1つ,3[m]1円を1つ,2[m]3円を2つ買うと,門松列列$(3,9,2,3)$を構成することができ,長さ$17$を得ます.

9[m]5円を1つ,4[m]3円を1つ,3[m]1円を1つ買っても門松列列$(9,3,4)$を構成することができますが,最適ではありません.

サンプル2
入力
5 30
2 2 2 2 2
1 3 5 7 9
出力
0

同じ高さの竹が複数あっても,🎍は作れません.

サンプル3
入力
4 11
1 2 3 4
1 1 1 1
出力
30

$(3,4,2,3,1,4,2,3,1,4,3)$

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