该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

差值游戏（diffgame）

题目描述

Y 同学正在玩一个数字游戏。

初始时有两个整数 $x,y$。此外，一共给出 $n$ 种操作。对于第 $i$ 种操作，给定三个整数 $a_i,b_i,c_i$，表示执行该操作需要花费 $c_i$，并且可以使当前的两个数发生以下两种变化之一：

• $(x,y)\to(x+a_i,\ y+b_i)$；
• $(x,y)\to(x+b_i,\ y+a_i)$。

每一种操作都可以被使用任意次。

Y 同学希望在若干次操作后，使得当前两个数满足

$\vert x-y\vert=m$。

但是在整个操作过程中，还必须始终满足差值限制：

$L \le x-y \le R$。

也就是说，初始状态以及每一次操作后的状态，都必须满足上述不等式。

你需要求出达到目标所需的最小总花费。若无法达到目标，则输出 $2147483647$。

输入格式

第一行包含两个整数 $x,y$。

第二行包含两个整数 $L,R$。

第三行包含两个整数 $n,m$，分别表示操作种数和目标值。

接下来 $n$ 行，第 $i$ 行包含三个整数 $a_i,b_i,c_i$，表示第 $i$ 种操作的参数。

输出格式

输出一行一个整数，表示最小总花费。

若无解，输出 $2147483647$。

样例

样例输入 #1

5 5
-2 5
5 5
3 -1 6
-4 -3 3
-2 -4 1
4 2 1
2 3 1

样例输出 #1

3

数据范围与约定

对于 $100\%$ 的数据，保证：$-10^3 \le x,y \le 10^3,-2\times 10^3 \le L \le R \le 2\times 10^3,0 \le m \le 2\times 10^3,0 \le n \le 2\times 10^3,-10^4 \le a_i,b_i \le 10^4,0 < c_i \le 10^4$。

• 特殊性质 A：保证 $L=-2000,\ R=2000$。
• 特殊性质 B：保证对所有 $1 \le i \le n$，均有 $a_i=b_i$。