该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

穿越到异界的冒险者发现，当地商队使用一套特殊的水晶货币：水晶的面值都是 3 的幂——1、3、9、27、81……（即 $3^0, 3^1, 3^2, 3^3, 3^4, \dots$）。

冒险者要支付恰好 n 个金币的货款。他手头有 m 种面值的水晶，第 i 种面值为 d[i]（保证都是 3 的幂），这种水晶他最多只有 c[i] 枚。请你帮忙算一算：要凑出恰好 n 个金币，最少需要用多少枚水晶？如果无论怎么组合都凑不出 n，输出 -1。

输入格式

第一行两个整数 n 和 m，分别是要凑的金额和水晶面值的种数。

第二行 m 个整数 d[i]，表示每种水晶的面值（都是 3 的幂，互不相同）。

第三行 m 个整数 c[i]，表示第 i 种水晶现有的枚数。

输出格式

一行一个整数：凑出 n 所需的最少水晶枚数；若无法凑出，输出 -1。

样例输入

100 7
1 3 9 27 81 243 729
100 100 100 100 100 100 100

样例输出

4

样例说明

100 可以用 81 + 9 + 9 + 1 凑出（共 4 枚），无法用更少的枚数。

数据范围

• 对于 100% 的数据：$1 \le m \le 38$，$0 \le n \le 10^{18}$，$1 \le d[i] \le 10^{18}$（d[i] 为 3 的幂），$0 \le c[i] \le 10^9$。