题目描述

这道题的背景知识来源于"项链相似度"问题。不过不用担心，我会为你提供所有需要的信息。

小猫再次思考他遇到的问题，并通过将$N \times (N + 1) / 2$个元素放入一个线性列表中，将其转化为一个全新的问题（其中$M = N \times (N + 1) / 2$）：

这里还出现了一个名为"Multi"的数组。假设给定"Pairs"和"Multi"数组，小猫的目标是确定一个包含$M$个整数的"Table"数组，该数组需要满足：

$$\text{Table}[i] \equiv \text{Pairs}[i] \ (\text{mod}\ \text{Multi}[i]) \quad (1 \leq i \leq M) $$

(这个条件与那个条件相似)

$$\sum_{i=1}^{M} \text{Table}[i]$$

（这个条件与"项链相似度"问题中出现的条件类似），并且使得：

尽可能大。此外，我们还必须满足$\text{Low}[i] \leq \text{Table}[i] \leq \text{Up}[i]$（对于任意$1 \leq i \leq M$）。这里的$\text{Low}$和$\text{Up}$是两个给定的包含$M$个整数的数组。

输入格式

输入包含多个测试用例。每个测试用例由以下部分组成：首先是一个整数$M$（$1 \leq M \leq 200$），随后是$M$行数据。第$i$行包含四个整数：$\text{Pairs}[i]$、$\text{Multi}[i]$、$\text{Low}[i]$、$\text{Up}[i]$。

限制条件：

• $-25 \leq \text{Low}[i] < \text{Up}[i] \leq 25$
• $0 \leq \text{Pairs}[i] \leq 100000$
• $1 \leq \text{Multi}[i] \leq 20$

根据输入数据，可以假设总是存在解。

输出格式

对于每个测试用例，输出一行，包含一个数字，即最大的：

$$\sum_{i=1}^{M} \text{Table}[i]$$

示例输入与输出

输入数据 1

10
7 1 1 10
0 2 -10 10
2 2 -10 10
0 2 -10 10
0 1 1 10
0 2 -10 10
0 2 -10 10
0 1 1 10
0 2 -10 10
0 1 1 10

10
0 1 1 10
2 2 -10 10
2 2 -10 10
2 2 -10 10
0 1 1 10
2 2 -10 10
2 2 -10 10
0 1 1 10
2 2 -10 10
0 1 1 10

输出数据 1

90
-4

来源

POJ Monthly--2006.01.22, Zeyuan Zhu