题目描述

众所周知，阿兔家开了一个工厂。多年之后，兔父将工厂交给阿兔管理。

工厂里有 n * n 大小的仓库，仓库最左上角为 1, 1，仓库在 x, y 位置有唯一的出货口，货物放置在出货口即为交付且货物移出仓库。 仓库里有 g 根柱子，货物和机械臂均不能移动到柱子上，货物初始也不会存在在柱子上。 出货口上方有一个机械臂，可以花费 1 秒上下左右移动、抓取货物或者放下货物，但在同一时刻仅可抓取一个货物。 机械臂可以升的很高，抓取货物的时候也可以移动到其他未抓取货物的上方。 由于货物易碎，所以机械臂不能将货物堆叠。

在某天，台州停电了，但是仓库内仍然存放了 m 个价值为 c 货物需要交付。 为了不被兔父骂，阿兔需要尽可能将这些货物交付出去。 阿兔开启了紧急发电机，但是发电机仅仅只能维持 k 秒。 请问阿兔在那一天最多还能交付价值多少的货物呢？

请你帮帮阿兔吧，机电学子。

输入格式

第1行输入 n， m， g， k， x， y，如题目所示。1≤n≤1e3， 1≤m,g,m+g＜min(n*n , 1e3)，1≤k≤1e5， 1≤x,y≤n 第2~m+1行输入 a， b， c，代表货物位于 a，b 位置且此物品价值为 c，保证两个货物不在同一个位置。1≤a,b≤n， 1≤c≤1e9 第m+2~m+g+1行输入 a， b，代表柱子位于 a，b 位置，保证两个柱子或与货物不在同一个位置。1≤a,b≤n

输出格式

输出1个整数，表示最多还能交付的货物价值。

3 4 3 17 2 3
1 1 9
2 1 3
3 1 12
2 3 100
2 2
3 2
3 3

112

提示

阿兔可以花费 12 秒拿取第 3 个货物，花费 0 秒交付第 4 个货物（因为它已经在出货口了）。 最多交付价值 112 的货物，没有比这更好的交付情况存在。