#背包dp ![[genshin.png]] > [!quote] 题目背景 > > 你说得对，但是[《原神》](http://ys.mihoyo.com)是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作“提瓦特”的幻想世界，在这里，被神选中的人将被授予“神之眼”，导引元素之力。你将扮演一位名为“旅行者”的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘“原神”的真相。 ## 题目描述 好渴鹅刚刚入坑了[原神](http://ys.mihoyo.com)，这个游戏是一个开放世界。为了简化问题，~~不让好渴鹅的脑子废掉~~，我们可以看做一共有 $n$ 个任务。对于第 $i$ 个任务，他需要 $l_i$ 的「冒险等阶」才可以做，做完之后会得到 $v_i$ 的经验。好渴鹅可以任意挑选，即不按照顺序来做。 由于是新账号，好渴鹅的「冒险阅历」只有 $0$ ，冒险等阶也只有 $1$ 级，每升一级需要 $1000$ 的冒险阅历。 你需要求出好渴鹅最多能通过做任务达到多少级。**注意：最高的冒险等阶只有 60 级**。 ## 输入格式 - 第 $1$ 行：一行一个 $n$ ，表示一共有 $n$ 个任务； - 第 $2$ 行：$n$ 个数，第 $i$ 个数为 $l_i$； - 第 $3$ 行：$n$ 个数，第 $i$ 个数为 $v_i$； ## 输出格式 一行一个 $ans$ ，表示好渴鹅最大能够达到的等级。 ## 提示说明 $n\le 2\times 10 ^ 5，\mathop{\forall}\limits_{i=1}^{n} ~ l_i\le 60，\mathop{\forall}\limits_{i=1}^{n} ~ v_i\le 10000$ **凉心提醒：** 不保证任务不重复。