献立作り C++編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 国には 5 つのビタミン 1,2,3,4,5 が存在します。
いま N 個の食材があります。
i 個目の食材は p_i 円で食べることができ、食べるとビタミン j (1 ≦ j ≦ 5) を v_{i,j} だけ摂取できます。
いまからあなたは献立を考えます。
献立に使う食材の集合を T としたとき、W = (W_1, W_2, W_3, W_4, W_5) を W_j = max(v_{i,j}) (i ∈ T) とします。
献立の魅力度を min(W_j) (1 ≦ j ≦ 5) と定義します。
また、献立の費用を Σ p_i (i ∈ T) 円と定義します。
費用が K 円以下の献立のうち、魅力度の最大値を出力してください。
ただし、費用が K 円以下の献立が存在しないなら -1 を出力してください。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N K
p_1 p_2 ... p_N
v_{1,1} v_{1,2} v_{1,3} v_{1,4} v_{1,5}
v_{2,1} v_{2,2} v_{2,3} v_{2,4} v_{2,5}
...
v_{N,1} v_{N,2} v_{N,3} v_{N,4} v_{N,5}
・ 1 行目には、食材の個数を表す整数 N、費用の上限を表す整数 K がこの順に空白区切りで与えられます。
・ 2 行目には、i 個目の食材の費用 p_i が空白区切りで与えられます。
・ 続く N 行の i 行目には、i 個目の食材を食べることで得られるビタミン j の量 v_{i,j} が空白区切りで与えられます。
・ 入力は合計で N+2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
費用が K 円以下の献立のうち、魅力度の最大値を出力してください。
ただし、費用が K 円以下の献立が存在しないなら -1 を出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 10^4
・ 1 ≦ K ≦ 10^9
・ 1 ≦ p_i ≦ 10^9
・ 0 ≦ v_{i,j} ≦ 10^9
- 入力例1
-
3 4
1 2 3
2 3 4 3 2
1 2 3 4 5
5 4 3 2 1
- 出力例1
-
2
- 入力例2
-
3 6
1 2 3
2 3 4 3 2
1 2 3 4 5
5 4 3 2 1
- 出力例2
-
4
- 入力例3
-
3 100
10000000 100000000 100000000
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
- 出力例3
-
-1
