条形蛋糕

题目描述

寒假到了，⼩杨同学打算找⼀份兼职，顺便体验⼀下打⼯⼈的⽣活。 ⼩杨同学给⼀家蛋糕店发送了⼀份⾃⼰的简历，希望可以在寒假来这⾥帮忙。店长最近正好遇到了⼀个难题：店⾥ 每天会做⼀条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？ 有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算⽤这个问题考⼀考⼩杨同学，问 题如下： 给定⼀条长度为 的长条蛋糕和⼀个价格表，该价格表表⽰长度为 （ ）的蛋糕块的价格为 。求 蛋糕的分割⽅案，使得总销售价格最⼤，注意蛋糕块的长度必须为整数。

输入格式

第⼀⾏⼀个正整数 （ ），表⽰长条蛋糕的总长度。 第⼆⾏ 个正整数 （ ），表⽰不同长度蛋糕块的价格。

输出格式

⼀⾏⼀个正整数，表⽰最⼤总销售价格。

样例输入 #1

4
1 5 8 9

样例输出 #1

10

样例输入 #2

10
1 5 8 9 10 17 17 20 24 30

样例输出 #2

30

样例解释 #1

第⼀个样例中，长度为 的蛋糕价值为 ，长度为 的蛋糕价值为 ，长度为 的蛋糕价值为 ，长度为 的蛋糕价 值为 ； 总长度为 的长条蛋糕，有 五种本质不同的分法。 其对应的总销售价格分别为 ，故最⼤总销售价格为 。 第⼆个样例中，长度为 的长条蛋糕，销售价格最⼤的分法为 ，最⼤总销售价格为 。

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。