{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problem statements in [Mandarin Chinese](https://www.codechef.com/download/translated/SNCKFL21/mandarin/ROBBERYPLAN.pdf), [Russian](https://www.codechef.com/download/translated/SNCKFL21/russian/ROBBERYPLAN.pdf), and [Vietnamese](https://www.codechef.com/download/translated/SNCKFL21/vietnamese/ROBBERYPLAN.pdf) as well.\n\nYou want to rob a jewellery store.\nThe jewellery store sells $n$ different types of jewels and for each type it has $10^9$ identical jewels of that type.\nA jewel of the $i$-th type weighs $i$ grams and is worth $a_i$ euros.\n\nYou plan to steal exactly $k$ jewels with a total weight of exactly $w$ grams (you can steal multiple jewels of the same type). What is the maximum possible total value, in euros, of the stolen jewels?\n"}},{"title":"Input Format","value":{"format":"MD","content":"- The first line contains the three integers $n$, $k$, $w$ — the number of types of jewels, the number of jewels you will steal, the total weight of the jewels you will steal. \n- The second line contains the $n$ integers $a_1, a_2, \\ldots, a_n$ — the values in euros of the jewels."}},{"title":"Output Format","value":{"format":"MD","content":"Print the maximum possible total value, in euros, of the stolen jewels if the robbery satisfies the constraints described in the statement."}},{"title":"Constraints","value":{"format":"MD","content":"- $1\\le n\\le 1\\,000$\n- $1\\le k\\le 10^6$\n- $k\\le w\\le kn$. Notice that under these constraints, one can show that there are $k$ jewels with a total weight equal to $w$.\n- $1\\le a_i\\le 10^9$ for all $i\u003d 1, 2,\\dots, n$."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2 4\n11 10 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e20\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nThere are $3$ types of jewels:\n\n1. The first type weighs $1$ gram and is worth $11$ euros.\n2. The second type weighs $2$ grams and is worth $10$ euros.\n3. The third type weighs $3$ grams and is worth $8$ euros.\n\nThe plan is to steal $2$ jewels with a total weight of $4$ grams. There are two valid choices of jewels to steal:\n\n- We may steal one jewel of type $1$ and one jewel of type $3$. In this way, the value of the stolen jewels would be $11 + 8 \u003d 19$.\n- We may steal two jewels of type $2$. In this way, the value of the stolen jewels would be $2\\cdot 10 \u003d 20$."}},{"title":"Sample 2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 6\n10 5 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e23\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nThe plan is to steal $3$ jewels with a total weight of $6$ grams. There are two valid choices of jewels to steal:\n\n- We may steal one jewel of type $1$, one jewel of type $2$, and one jewel of type $3$. In this way, the value of the stolen jewels would be $10 + 5 + 8\u003d23$.\n- We may steal three jewels of type $2$. In this way, the value of the stolen jewels would be $3\\cdot 5 \u003d 15$."}},{"title":"Sample 3","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1000000 1994294\n454353453 941594523\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e938814325454580\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nThere is only one valid choice of jewels to steal: $5706$ jewels of type $1$ and $994294$ jewels of type $2$. In this way, the value of the stolen jewels would be $5706\\cdot 454353453 + 994294\\cdot 941594523 \u003d 938814325454580$.\n"}},{"title":"Sample 4","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 11 40\n15 14 14 12 12\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e146\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nThere are many valid choices of jewels to steal, one of the optimal choices (i.e., one of the choices which achieves the maximum total value of $146$) is: one jewel of type $2$, six jewels of type $3$, four jewels of type $5$."}}]}