# 题目描述

「暮念」正在教「瑄瑄」玩一款风靡全国的名为《农》的 MOBA 类游戏，现在进行新手教程，系统为「瑄瑄」安排了一名由她操控的英雄「妲己」和 $n$ 个敌方小兵。游戏规则如下：

1. 「妲己」每秒可以对一个小兵造成固定 $A$ 点伤害；第 $i$ 个小兵的生命值为 $H_i$，如果第 $i$ 个小兵存活（即 $H_i>0$），每秒钟会对「妲己」造成 $D_i$ 点伤害。

2. 每一秒中，在小兵对「妲己」造成伤害之后，「瑄瑄」可以操控「妲己」对一个存活的小兵 $i$ 进行攻击，使 $H_i$ 减少 $A$，当 $H_i≤0$ 时，该小兵阵亡。击杀所有小兵即可通过新手教程。

由于是新手教程，「妲己」无论受到多少伤害都不会死亡，但是「暮念」要求使「妲己」尽可能少地受到伤害，否则就要狠狠地惩罚「瑄瑄」。

请你计算出「妲己」受到的最少伤害，帮助「瑄瑄」通过新手教程而不被惩罚。

# 输入格式

第一行输入 $1$ 个整数 $A$ 和 $1$ 个整数 $n$，$1≤A≤10^9$，$1≤n≤10^5$。

第二行输入 $n$ 个整数 $D_i$，$1≤D_i≤10^9$。

第三行输入 $n$ 个整数 $H_i$，$1≤H_i≤10^9$。

# 输出格式

输出 $1$ 个整数，表示「妲己」受到的最少伤害。数据保证这个数一定在 long long 范围内。

# 输入样例 1

4 4

1 2 3 4

4 5 6 8

# 输出样例 1

39

# 输入样例 2

1 4

1 1 1 1

1 2 3 4

# 输出样例 2

20

# 输入样例 3

8 1

40

59

# 输出样例 3

320

# 题解：贪心 + 排序

首先考虑是逐个击破好还是雨露均沾好。对于两个敌人，不论是逐个击破还是雨露均沾，第二个敌人阵亡的时间都是不变的，对玩家的伤害也是固定的，而雨露均沾会拉长对第一个敌人的战线，使其对玩家造成更高的伤害。由此可见，逐个击破才是最佳策略。

接下来我们要考虑按照什么顺序逐个击破。考虑到敌人的伤害同时受到血量和伤害的影响，我们考虑将它们按照一定指标排序，这就要用到贪心里的邻项交换法了。考虑 $i, j$ 两个敌人，假设先打 $i$ 受到的伤害比先打 $j$ 受到的伤害小，则我们可以列出如下不等式：

$$\left\lceil \frac {H_1} A \right\rceil (D_1 + D_2) + \left\lceil \frac {H_2} A \right\rceil D_2 < \left\lceil \frac {H_2} A \right\rceil (D_1 + D_2) + \left\lceil \frac {H_1} A \right\rceil D_1 \\ \left\lceil \frac {H_1} A \right\rceil D_2 < \left\lceil \frac {H_2} A \right\rceil D_1 \\ \frac {\left\lceil \dfrac {H_1} A \right\rceil} {D_1} < \frac {\left\lceil \dfrac {H_2} A \right\rceil} {D_2}$$

因此我们将 $n$ 个敌人按照 $\dfrac {\left\lceil \dfrac {H_i} A \right\rceil} {D_i}$ 从小到大排序，逐个击破，受到的伤害最小。

注意到数据范围有 $10^9$，浮点数误差不可忽略，所以我们要尽可能避免浮点数计算。具体来说：

1. $\left\lceil \dfrac a b \right\rceil = \left\lfloor \dfrac {a - 1} b \right\rfloor + 1$；

2. 将分式不等式写作交叉相乘的形式。

时间复杂度：$O(n \log n)$。

参考代码：

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define EPS 1e-6

typedef long long ll;

int A, n, d[100010], h[100010];

ll time, harm;

struct Enemy

{

    int d, h;

} enemy[100010];

int Cmp(const void *a, const void *b)

{

    struct Enemy x = *(struct Enemy*)a;

    struct Enemy y = *(struct Enemy*)b;

    if (1ll * ((x.h - 1) / A + 1) * y.d > 1ll * ((y.h - 1) / A + 1) * x.d)

        return 1;

    else

        return -1;

}

int main()

{

    // freopen("T.in", "r", stdin);

    // freopen("T.out", "w", stdout);

    scanf("%d%d", &A, &n);

    for (int i = 1; i <= n; ++ i)

        scanf("%d", &enemy[i].d);

    for (int i = 1; i <= n; ++ i)

        scanf("%d", &enemy[i].h);

    qsort(enemy + 1, n, sizeof(enemy[1]), Cmp);

    for (int i = 1; i <= n; ++ i)

    {

        time += ((enemy[i].h - 1) / A + 1);

        harm += time * enemy[i].d;

    }

    printf("%lld\n", harm);

    return 0;

}