U76029 货币系统

有 $n$ 种面额的货币，第$i$ 种货币的面额为 $a[i]$，每种货币有无限多张。给定整数 $x,k$，你想要选出尽量多的**连续段**，使得： 1. 每段中的面额都可以把 $x$ 这个数表示出来； 2. 每一段的长度不超过 $k$。 即：选出尽量多长度 $\le k$ 且能表示 $x$ 的互不重叠段 例如 $n = 5, x = 5, k = 2, a = [1,2,3,4,5]$ 那么可以找出3段：$[1][2,3][4,5] $ 使得每段内的货币系统中 $x=5$ 都可以被表示出来: - 5 = 1 + 1 + 1 + 1 + 1 - 5 = 2 + 3 - 5 = 5 又例如 $n = 5, x = 5, k = 2, a = [5,3,6,2,3]$ 那么可以找出2段：$[5][2,3] $

无

无

对于30%的数据 $n\le 10, a[i],x\le 10, k = n$ 对于60%的数据 $n\le 100, a[i],x\le100, k = n$ 对于100%的数据 $1\le n\le 1000, 0\le a[i],x,k\le10000$