题目描述

小 X 来到一个雄奇的金字塔挖宝，但是这是一座被诅咒的金字塔，小 X 必须马上逃离这里，否则小 X 就会被埋在金字塔里，但他不希望此行落空。

现在小 X 面前有 $N+1$ 种财宝，每种财宝都有一个价值。第一种财宝重量为 $0$，第二种财宝重量为 $1$，总之第 $I$ 种财宝重量为 $I-1$。现在小 X 希望拿走 $N+M$ 个物品，但是这 $M+N$ 个物品总重量不能超过 $N$。小X希望能获得最大的价值。你能帮帮他吗？

由于金字塔跟小 X 一样牛，所以每种财宝无限个。

输入格式

第一行两个正整数 $N,M$

第二行 $N+1$ 个整数，第 $I$ 个整数代表了第 $I$ 种财宝的价值

输出格式

一个数，表示最大利润。

5 3
4 7 2 5 -3 6

47

数据范围

$10\%$ 满足 $N,M \le 10$

$40\%$ 满足 $N,M \le 100$

$100\%$ 满足 $N,M \le 3000$，$| 财宝价值 | \le 1000$