解题思路

对于每个张量，都有两种释放方式：$swap$ 或者 重计算。 但无论选哪一种，这个张量都只能贡献一次可释放空间，大小都是对应的张量大小。

所以对第 $i$ 个张量而言：

• 可释放空间为 $a_i$
• 释放代价为 $\min(b_i, c_i)$

题目内容

在大模型训练中，为解决 $NPU$ 显存不足的问题，通常采用张量 $swap$ 或者张量重计算的方式进行优化；张量 $swap$ 是把张量的数据先搬到 $CPU$ ，需要的时候，再从 $CPU$ 搬回 $NPU$ ；张量重计算是在需要张量的值时，在 $NPU$ 上重新把张量的值计算出来。

• 假设把模型部署在 $NPU$ 上，还需要 $m$ 大小的存储空间，才能让大模型运行起来；
• 目前有 $n$ 个候选张量，每个张量占用一定的存储空间；
• $n$ 个张量中的每个张量都可以进行 $swap$ 或者重计算， $swap$ 和重计算分别对应不同的代价；

试着编写一段程序，从 $n$ 个候选张量中选择合适的张量进行 $swap$ 或者重计算，在代价最小的情况下，使得大模型能够运行起来（选择的张量和大于等于 $m$ ）。

输入描述

第一行为 $1$ 个整数 $m(0<m<10000)$，表示需要的存储空间大小

第二行为 $1$ 个整数 $n(0<n<10000)$，表示候选张量的个数

第三行有 $n$ 个处于区间 $[1, 100000]$ 之内的整数，表示 $n$ 个候选张量的存储空间大小

第四行有 $n$ 个处于区间 $[1, 100000]$ 之内的整数，表示 $n$ 个候选张量 $swap$ 的代价

第五行有 $n$ 个处于区间 $[1, 100000]$ 之内的整数，表示 $n$ 个候选张量重计算的代价

输出描述

如果没有找到合适的解，输出 $error$ ；否则，输出最小代价（行尾没有空格）。

样例1

输入

10
5
3 4 5 6 7
1 2 3 5 5
2 3 4 5 6

输出

6

说明

需要的存储空间是 $10$ ；

候选张量长度分别为 $3，4，5，6，7$；

张量长度组合 $3+7，4+6，5+6，5+7，6+7，3+4+5，...$ 都大于等于 $10$ ，满足运行的基本条件；

对于 $3+7$ 来说，$3$ 的最小代价是 $1$，$7$ 的最小代价是 $5$ ，$3+7$ 的最小代价是 $6$；

经过其他组合的比较，达到目标的最小代价是 $6$ ，所以输出 $6$ 。

样例2

输入

12
4
18 20 10 12
12 3 13 4
10 14 10 1

输出

1

说明

需要的存储空间是 $12$；

候选张量长度分别为 $18，20，10，12$；

张量长度 $18，20，12$ 都大于等于 $12$ ，满足运行的基本条件；

其中 $12$ 的代价最小为 $1$ ，所以输出 $1$ 。