You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

最近家里断网了，徐老师真的非常无聊

于是石老师给徐老师设计了一个很有(wu)趣(liao)的游戏

石老师会先给出徐老师两个数字 $x,y$

为了让徐老师能够玩的有意思一些，石老师指定了 $n$ 个不同的变化规则

对于第 $i$ 个操作有三个属性 $a,b,c$，使用这个操作需要花费 $c$，可以使得数字发生以下两个变化之一

1. $x+a,y+b$
2. $x+b,y+a$

而游戏的目标是用最小的花费使得 $x,y$ 的差值刚好等于 $m$，即 $|x-y|=m$

但是这个游戏对于徐老师来说太简单了，于是石老师又给出了新的规则：

在游戏过程中，$x-y$（无绝对值） 的值必须一直保持在 $[L,R]$ 的范围内，即 $L \leq x - y \leq R$

现在徐老师正在玩这个游戏，他想知道最终的答案是多少，以此验证自己的做法是否正确

P.S. 每一个操作可以无限次数使用

输入格式

输入第一行包含两个整数 $x,y$，含义如题

输入第二行包含两个整数 $L,R$，含义如题

输入第三行包含两个整数 $n,m$，表示游戏有 $n$ 种操作，目标值是 $m$

接下来 $n$ 行，每行包含三个整数 $a_i,b_i,c_i$ 分别表示第 $i$ 种操作的三个属性

输出格式

输出一行，表示最小的花费，如果无解则输出 $2147483647$，即 $2^{31}-1$

数据范围

对于前 $30\%$ 的数据：$-20\leq x,y \leq 20,-2 * 10^3 \leq L \leq R \leq 2 * 10^3,n \leq 10$，保证答案不超过 $100$；

对于另外 $30\%$ 的数据：$-100\leq x,y \leq 100,L=-2 * 10^3,R=2 * 10^3,n\leq100$，保证数据随机。

对于 $100\%$ 的数据：$-10^3\leq x,y \leq 10^3,-2 * 10^3 \leq L \leq R \leq 2 * 10^3,0\leq m \leq 2 * 10^3,0 \leq n \leq 2 * 10^3,-10^4 \leq a_i,b_i \leq 10^4,0 < c_i \leq 10^4$．

样例输入

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

样例输出

3

样例解释

先进行 $3$ 号操作，$x+(-2)=3,y+(-4)=1$，花费 $1$ 再进行 $4$ 号操作，$x+4=7,y+2=3$，花费 $1$ 再进行 $5$ 号操作，$x+3=10,y+2=5$，花费 $1$ 达到目标值 $|x-y|=m=5$，最小花费为 $3$