题目描述

糖果厂要将生产的 $n$ 颗糖果装成若干袋进行销售，每袋必须恰好装满 $k$ 颗糖果。已知每袋恰好装 $k$ 颗糖果时，这袋糖果的售价为 $a_k$ 元。

所有糖果都必须装入袋中，不能有剩余。请你计算如何分装才能使所有糖果的总售价最高。

输入格式

第一行，一个正整数 $n$，表示糖果的总颗数。

第二行，$n$ 个非负整数 $a_1, a_2, \ldots, a_n$，表示不同规格糖果袋的售价。

输出格式

输出共一行，一个整数，表示所有分装方案中，糖果的最高总售价。

输入样例 #1

4
1 5 6 3

输出样例 #1

10

数据范围

对于 $40\%$ 的测试点，保证 $1\le n\le 10$。

对于所有测试点，保证 $1\le n\le 1000$，$0\le a_i\le 10^4$。