题目描述

兔猫信奥学院的小兔和小猫在加菲老师的实验室发现了一排神奇的能量方块，每个方块都有一个能量值（用整数数组nums表示）。为了启动实验室的超级计算机，他们需要收集总能量恰好为x的能量。

游戏规则如下：

1. 每次只能从方块序列的最左端或最右端取走一个方块
2. 取走的方块能量会从x中扣除
3. 方块序列会实时更新（取走后就消失了）
4. 目标是用最少的操作次数使x正好减到0

加菲老师看着困惑的小兔和小猫，决定把这个难题交给信奥学院的学员们来解决。你能帮助他们找到最少操作次数吗？如果无法完成目标，请返回-1。

输入格式

第一行包含一个整数n，表示能量方块的数量 第二行包含n个整数，表示每个方块的能量值nums[i] 第三行包含一个整数x，表示需要收集的总能量值

输出格式

输出一个整数，表示最少操作次数。如果无法完成目标，输出-1

输入样例1

5
1 1 4 2 3
5

输出样例1

2

输入样例2

5
5 6 7 8 9
4

输出样例2

-1

输入样例3

6
3 2 20 1 1 3
10

输出样例3

5

数据范围

• 1 ≤ n ≤ 10^5 • 1 ≤ nums[i] ≤ 10^4 • 1 ≤ x ≤ 10^9