J17 实践-1 美味指数

题目描述

佩奇要从猪猪星球飞到地球，现在要准备食物。 一共有 $n$ 件食材，每件食材有三个属性，$a_i$，$b_i$ 和 $c_i$ ，如果在 $t$ 时刻完成第 $i$ 样食材则得到 $a_i-t*b_i$ 的美味指数，用第 $i$ 件食材做饭要花去 $c_i$ 的时间。 但佩奇的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大。

输入格式

第一行是两个正整数 $T$ 和 $n$，表示到达地球所需时间和食材个数。 第二行 $n$ 个整数：$a_i$； 第三行 $n$ 个整数：$b_i$； 第四行 $n$ 个整数：$c_i$。

输出格式

一个整数，表示最大的美味指数。

样例输入

74 1
502
2
47

样例输出

408

样例分析

如上所述。

数据范围

对于 $40\%$ 的数据：$1 \le n \le 10$； 对于 $100\%$ 的数据：$1 \le n \le 50$； 所有数字均小于 $100,000$。