Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
近年狼の国では、1 円玉が廃止され、最小額の硬貨が 5 円玉となり、全ての貨幣の額面が 5 の倍数になりました。 しかし、商品の値段は未だに 5 の倍数でないものが存在しています。
狼の国に遊びに来たすぬけ君は、ある店で N 個の商品全てを買うことにしました。i 番目の商品の値段は p_i 円です。
この国には 1 円玉がないので、幾つかの商品をレジに持っていくと、持って行った商品の値段の合計を 5 で割ったあまりを v としたとき、v が 1 または 2 ならばそれぞれ 1 円、2 円引きになり、3 または 4 ならばそれぞれ 2 円、1 円が合計金額に上乗せされます。v が 0 ならば合計金額はそのままです。
ところがすぬけ君は、N 個の商品を何回かに分けてレジに持っていくと、持っていく方法によって支払う金額の総計が変わる可能性があることに気がつきました。 すぬけ君は可能な限り節約したいので、適切な方法でレジに持っていくことで、N 個全ての商品を買うのに払う金額の総計を最小化したいです。 ただし、レジに何度も商品を持っていくのはあまりに疲れる行為なので、金額の総計が最小な中でレジに持っていく回数を最小化したいです。
すぬけ君が払う金額の総計の最小値と、そのうちレジに持っていく回数の最小値を求めてください。
制約
- 1 ≤ N ≤ 10^6
- 1 ≤ p_i ≤ 1000
- 入力で与えられる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N p_1 : p_N
出力
すぬけ君が払う金額の総計の最小値と、そのうちレジに持っていく回数の最小値をスペース区切りで出力せよ。
入力例 1
6 1 1 2 1 2 1
出力例 1
0 4
- 1 番目の商品と 2 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
- 4 番目の商品と 6 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
- 3 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
- 5 番目の商品をレジに持っていくと、合計金額から 2 円引きとなり、0 円になります。
以上により、総計 0 円をレジに 4 回持っていくことで達成できます。
入力例 2
5 968 127 125 966 861
出力例 2
3045 1
全ての商品を一度にレジに持っていくのが最適です。