# 生成序列中的预算选择

预估时间限制：1.0 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

一个回收站用简短参数生成一整批物资的处理费用。部分物资可以带来返款，因此费用可能为负。站点希望在预算内处理尽可能多的物资。

(本故事由GPT-6重写)

## 形式化问题描述

给定 $n,A,B,C,D,L$ .令 $x_0=A$ ，对 $i=1,\ldots,n$ 依次生成

$$x_i=C+\operatorname{rem}(x_{i-1}B,D)$$

其中 $\operatorname{rem}(u,v)=u-\operatorname{trunc}(u/v)v$ ，除法向零截断，$D\ne0$ .余数为零或与 $u$ 同号；$D$ 可以为负。生成过程中使用精确整数乘法，不进行 32 位环绕。

从 $x_1,\ldots,x_n$ 中选择若干不同位置，使其值之和不超过 $L$ ，求能选中的最多位置数。同值位置可以同时选择，空集的和为零。如果连一个满足预算的集合都不存在，约定输出 $0$ .因此在负预算下，输出零不一定表示空集满足预算。

## 输入格式

第一行五个整数 $n,A,B,C,D$ .第二行一个整数 $L$ .

## 输出格式

输出一行一个整数，表示最多选择的位置数；不存在可行集合时按约定输出零。

## 样例

### 样例 1

### 输入

```text
5 3 4 5 19
20
```

### 输出

```text
2
```

### 样例 2

### 输入

```text
4 0 1 -2 100
-10
```

### 输出

```text
4
```

### 样例 3

### 输入

```text
3 0 0 1 7
-1
```

### 输出

```text
0
```

## 样例解释

样例 1 生成 17、16、12、3、17，选择 3 与 12，费用为 15；最便宜的三个值之和为 31，超过预算 20。样例 2 生成 -2、-4、-6、-8，全部选中后的和为 -20，满足预算 -10。样例 3 的所有值都是 1，预算为 -1，没有可行集合。

![样例1排序后选择最便宜的两个值](assets/budget.svg)

选择两个位置的最低费用为 15，选择三个位置至少需要 31。

## 数据范围与保证

所有数据满足 $1\le n\le2\times10^7$ ，$|A|,|B|,|C|,|D|,|L|\le10^9$ ，$D\ne0$ .

规格由 Codex（GPT-6）重新设计：明确序列递推、负数余数、非零除数和无可行集合时的输出。

| 分值比例 | 额外条件 |
| --- | --- |
| 20% | $n\le20$ |
| 30% | $n\le100000$ |
| 50% | 无额外条件 |