背包dp

题目背景

你说得对,但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作“提瓦特”的幻想世界,在这里,被神选中的人将被授予“神之眼”,导引元素之力。你将扮演一位名为“旅行者”的神秘角色,在自由的旅行中邂逅性格各异、能力独特的同伴们,和他们一起击败强敌,找回失散的亲人——同时,逐步发掘“原神”的真相。

题目描述

好渴鹅刚刚入坑了原神,这个游戏是一个开放世界。为了简化问题,不让好渴鹅的脑子废掉,我们可以看做一共有 个任务。对于第 个任务,他需要 的「冒险等阶」才可以做,做完之后会得到 的经验。好渴鹅可以任意挑选,即不按照顺序来做。

由于是新账号,好渴鹅的「冒险阅历」只有 ,冒险等阶也只有 级,每升一级需要 的冒险阅历。

你需要求出好渴鹅最多能通过做任务达到多少级。注意:最高的冒险等阶只有 60 级

输入格式

  • 行:一行一个 ,表示一共有 个任务;
  • 行: 个数,第 个数为
  • 行: 个数,第 个数为

输出格式

一行一个 ,表示好渴鹅最大能够达到的等级。

提示说明

凉心提醒: 不保证任务不重复。