004 - ありすぬーんてぃー

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 7 /


TLE
1sec
MLE
64MB
得点
100

概要(ストーリー)

仲良し五人組のAfterとShinoとKarenとAyayaとYokoがAlicenoonTeaを開催したんだ。



Alicenoonになり、開始直前となった今、ある事実が発覚したんだ。
紅茶に使う数種類のジャムの量が足りないんだ。
さあ困ったんだ。
各人がそれぞれ好きな種類のジャムの量が足りないと、不満度が増加していくんだ。
ある程度不満度がたまると、その人はプンプンになって家に帰ってしまうんだ。
そこで、「ジャムのプロ」である貴方は、誰も怒って帰らない且つ全員の合計不満度が最小となるようにジャムを振り分けることを決意したんだ。

んだ!

問題

ジャムの種類はM個あり、それぞれjami(g)存在する。
五人の好きなジャムの種類kindはこのi個の内のどれかである。
好きなジャムがn(g)足りないと、不満度は(2^(n+1))*(2^(hate+1))増加する。
好きなジャムが足りる場合は、不満度は0になる。
そして、不満度がmaxを超えると、その人は家に帰ってしまう。
誰も帰らず、且つ不満度の合計の最小を求め、出力せよ。
ジャムの量が絶対的に足りず、達成が不可能な場合は、"Hello!"と出力せよ。

制約

1 ≦ M ≦ 10
0 < Jamm < 1000
1 ≦ kind ≦ m
0 < w < 10
0 < hate < 10
0 < max < 100000

入力形式

ジャムの種類の数m、それぞれのジャムの量Jam、五人のそれぞれ好きなジャムの種類kindと量w、不満増加率hate、我慢の限界値maxが与えられる。

例)
m
Jam1
   .
   .
   .
Jamm
kind1 w1 hate1 max1
kind2 w2 hate2 max2
   .
   .
   .
kind5 w5 hate5 max5

さんぷる入力1

2
10
5
1 4   1   1
1 6   6   1
2 3   9   1
2 1   7   1
2 2   3 898

さんぷる出力1

64

さんぷる入力2

5
20
3
12
2
1
1 5 2 1
2 5 4 1
3 6 7 1
4 2 9 1
5 9 9 2

さんぷる出力2

Hello!

さんぷる入力3

5
999
5
5
10
0
2 5 2    1
2 3 5 1024
2 4 2  256
3 5 8    1
3 5 1  256

さんぷる出力3

1536

さんぷる3解説

[Jam2]
二人目 : n=3, hate=5 :  2^4*2^6 = 16*64 = 1024(ギリギリ足りる)
三人目 : n=4, hate=2 :  2^5*2^3 = 32*8  =  256(ギリギリ足りる)
[Jam3]
五人目 : n=5, hate=1 :  2^6*2^2 = 64*4  =  256(ギリギリ足りる)
となるので、誰も帰らずに済み、
1024+256+256 = 1536
となるので、合計不満度は1536となる。






後日談

ありすおいしい。