争先红葫芦

题目描述

Y 同学正在进行一场战斗。

他的角色拥有气血值，气血上限为 $x$，初始气血值也为 $x$。当角色的气血值降低到 $0$ 或以下时，角色会立即被击败。

Y 同学拥有一个可以使用至多 $n$ 次的道具。这个道具每次使用的效果如下：

• 第一次使用：直接将当前气血值恢复至 $x$；
• 从第二次使用开始：每次恢复 $\left\lfloor\dfrac{x}{3}\right\rfloor$ 点气血。

任何一次恢复后，气血值都不会超过上限 $x$。也就是说，若恢复后的气血值大于 $x$，则实际气血值变为 $x$。

敌人一共会进行 $m$ 次攻击。第 $i$ 次攻击会使 Y 同学的气血值减少 $a_i$。

每次攻击结束后：

• 如果当前气血值已经小于等于 $0$，Y 同学立即被击败，不能再使用道具恢复；
• 如果仍然存活，则可以使用若干次道具，也可以不使用。

所有攻击按照 $1,2,\dots,m$ 的顺序依次进行，道具在整个战斗过程中累计最多使用 $n$ 次。

Y 同学会合理选择使用道具的时机，使自己尽可能晚被击败。

请你判断 Y 同学能否坚持到全部 $m$ 次攻击结束。

如果会被击败，输出第一次必然被击败时对应的攻击编号；如果能够坚持到战斗结束，则输出 $-1$。

输入格式

第一行包含三个整数 $x,n,m$，分别表示气血上限、道具最多可以使用的次数以及敌人的攻击次数。

第二行包含 $m$ 个整数 $a_1,a_2,\dots,a_m$，其中 $a_i$ 表示第 $i$ 次攻击造成的伤害。

当 $m=0$ 时，第二行可以为空。

输出格式

如果 Y 同学会被击败，输出一行一个整数，表示他被击败时的攻击编号。

如果能够坚持到全部攻击结束，则输出 $-1$。

样例

样例输入 #1

100 4 5
50 45 60 60 70

样例输出 #1

-1

样例输入 #2

100 100 1
101

样例输出 #2

1

样例输入 #3

100 0 5
1 1 98 1 1

样例输出 #3

3

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le x\le100$；
• $0\le n,m\le100$；
• $0\le a_i\le10^9$。

• 特殊性质 A：保证 Y 同学一定不会被击败。
• 特殊性质 B：保证 $x=1$。
• 特殊性质 C：保证 $n=0$。