3913: 张老师的无聊游戏
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
最近家里断网了，张老师真的非常无聊
于是石老师给张老师设计了一个很有(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. 每一个操作可以无限次数使用
于是石老师给张老师设计了一个很有(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$ 种操作的三个属性
输入第二行包含两个整数 $L,R$，含义如题
输入第三行包含两个整数 $n,m$，表示游戏有 $n$ 种操作，目标值是 $m$
接下来 $n$ 行，每行包含三个整数 $a_i,b_i,c_i$ 分别表示第 $i$ 种操作的三个属性
对于前 $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$．
对于另外 $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$．
输出
输出一行，表示最小的花费，如果无解则输出 $2147483647$，即 $2^{31}-1$
样例输入 复制
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$
再进行 $4$ 号操作，$x+4=7,y+2=3$，花费 $1$
再进行 $5$ 号操作，$x+3=10,y+2=5$，花费 $1$
达到目标值 $|x-y|=m=5$，最小花费为 $3$