がっちょ君はN面の畑とM個の芋を所有している。各畑にはそれぞれ1からNまでの番号が付けられている。がっちょ君は畑に芋を植え収穫することで、芋の数を増やしたいと考えている。
がっちょ君は一人暮らしであり、1人ではK面までの畑しか管理することができない。また、各畑の土の状態や面積は様々で、芋の収穫数や植えることのできる芋の数も様々である。芋を畑iに植えた場合、1年後には畑iに植えた芋1つにつきai個の芋を収穫することができる。ただし、畑iには最大でもbi個の芋しか植えることができない。
がっちょ君がK面以内の畑にM個以内の芋を植えた時、1年後に所有することができる芋の数の最大値を求めてほしい。
入力は以下の形式で与えられる。
N M K a1 a2 ... aN b1 b2 ... bN
1行目に3個の整数N, M, Kが空白区切りで与えられる。
2行目にN個の整数aiが空白区切りで与えられる。
3行目にN個の整数biが空白区切りで与えられる。
芋の数の最大値を1行で出力せよ。
5 100 3 2 3 4 5 6 50 40 20 10 5
280
畑1に40個、畑2に40個、畑3に20個植えることで収穫後に280個の芋を所有することができる。
5 100 3 2 3 4 5 100 50 40 20 10 1
339
畑2に40個、畑3に20個、畑5に1個植えることで300個の芋を収穫することができ、植えなかった芋と合わせて答えは339になる。