问题 D: 4.游戏智商 (game)

问题 D: 4.游戏智商 (game)

题目描述

  熊的智商高还是猴子的智商高,这或许是一个很难考究的问题。故事里,吉吉国王一直标榜自己是最聪明最伟大的猴子国王,他的毛毛也是这么坚信。而我们的熊大和熊二却一直相信他们熊熊才是最聪明的。于是,在导游光头强的建议下,他们决定来一场 pk。
Pk 的内容是这样的,有 n 个格子,每个格子从左到右的编号依次是 1 到 n(编号也是位置),每个格子上都有不同美味值的水果(猴子们和熊们都很喜欢吃水果,所以水果对他们来说很有吸引力)。他们从位置 0 开始出发,手上有 AB 两种卡片,A 卡有 na 张,B 卡片有nb 张。每次他们可以用掉一张卡片,然后往前跳若干格,跳的格子数就是卡片上的数字。
每跳到一个格子上,就可以吃掉对应格子里面的水果,获得水果的美味值。当然了,我们会保证当卡片用完的时候,一定刚好跳到第 n 个格子上。卡片一定要用完,不能有剩余。游戏的结果就是在相同的情况下,谁能获得的水果美味值总和最大。熊熊们想要赢得这个比赛,于是熊二请求你的帮助。如果你可以帮助他算出最大值,他甚至可以把他最心爱的蜂蜜分享给你。


输入

输入第一行是 3 个整数 n,na,nb,va,vb,n 表示格子的总数,na 表示 A 种卡片的数量,nb 表示 B 种卡片的数量,va 表示 A 种卡片上的数,vb 表示 B 种卡片上的数。保证 n 一定等于 na*va+nb*vb。
接下来 n 个整数,表示每个格子上水果的美味值,注意美味值有可能是负数。


输出

输出只有一行一个整数,表示卡片用完的时候,最多可以得到的美味值总和。

样例输入输出

输入#1 复制
3 1 1 2 1
1 2 3
输出#1 复制
5
输入#2 复制
4 2 1 1 2
4 3 2 1
输出#2 复制
8

提示

【样例 1 解释
先用 1 再用 2,美味值是 4,先用 2 再用 1,美味值是 5。

【样例 2 解释
先用两个 1,再用 2,可以得到的值是 8。

【数据范围约定】
共计有 20 个测试点。
对于第 1-6 个测试点,保证 na=1,nb<=200,美味值都是小于等于 10000 的正整数。
对于第 7-12 个测试点,保证 1<=na,nb<=12,美味值的绝对值小于等于 10000。
对于 100%的数据,保证 1<=n<=20000,1<=na,nb<=2000,1<=va,vb<=5,va 不等于 vb,美味值的绝对值不超过 1000000。


序号 标题 作者 发表时间 费用 订购数 操作