CF2038A Bonus Project

有 $n$ 名编号为 $1$ 到 $n$ 的软件工程师。他们的老板承诺，如果他们完成一个额外项目，将给他们发放奖金。完成这个项目总共需要 $k$ 个单位的工作。给第 $i$ 名工程师的奖金是 $a_i$ 。第 $i$ 名工程师估计他们的一个单位的工作价值为 $b_i$ 。如果奖金发放了，那么第 $i$ 名工程师完成 $c$ 个单位的工作的收益 $s_i$ 定义为 $s_i = a_i - c \cdot b_i$。如果奖金不发放，工程师将不会自愿做任何工作。工程师们已经一起工作了很多年，所以他们知道奖金将如何分配，以及他们的同事对劳动的估值是多少。也就是说，团队中的每个工程师都知道所有的 $a_i$ 和 $b_i$。工程师们渴望得到奖金，所以他们同意按照以下过程在他们之间分配工作： - 第一名工程师说：“我将完成 $c_1$ 个单位的工作”，其中 $c_1$ 是一个非负整数； - 然后，第二名工程师说：“我将完成 $c_2$ 个单位的工作”，其中 $c_2$ 是一个非负整数； -... 以此类推； - 最后，第 $n$ 名工程师说：“我将完成 $c_n$ 个单位的工作”，其中 $c_n$ 是一个非负整数。 每个工程师都会说出一个 $c_i$ 来最大化他们自己的收益 $s_i$。如果预期的收益为零，工程师仍然会同意工作以获得经验并帮助他们的同事获得奖金。然而，如果出于某种原因预期的收益为负（工程师需要进行过量的工作，或者项目无法完成），那么该工程师将不会进行任何工作（完成0个单位的工作）。假设每个工程师的行为都是完美的，你的任务是找出每个工程师所说的数字 $c_i$。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 1000$；$1 \leq k \leq 10^6$），分别表示公司中的工程师人数和项目所需的工作单位数。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示如果项目完成，将支付给第 $i$ 位工程师的奖金。第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 1000$），其中 $b_i$ 表示第 $i$ 位工程师的工作单位成本。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 1000$；$1 \leq k \leq 10^6$），分别表示公司中的工程师人数和项目所需的工作单位数。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示如果项目完成，将支付给第 $i$ 位工程师的奖金。第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 1000$），其中 $b_i$ 表示第 $i$ 位工程师的工作单位成本。

在这两个例子中，工程师们分配了工作并获得了奖金，即使第三个工程师的收益为零。在第二个例子中，奖金项目需要太多工作量才能完成，所以工程师们根本不工作反而更有益。