Description

小z准备举办一个比赛。他需要提供一些甜点给参赛者来补充能量。每种甜品有一定的能量 $t_i$ 和大小 $u_i$，且每种甜点最多有 $v_i$ 个。

小z准备用箱子来包装甜点。箱子可以容纳一定体积的甜点且需要一定的费用。小z有一种魔法，可以将一个甜点分成多份装在箱子里，最后再合在一起（但合成之后必须是完整的一个）。

小z想知道准备能量至少为P的甜点的最小大小和最少需要多少费用来购买箱子，如果最少费用超过小z所拥有的钱数k则输出FAIL。

Input Format

第一行为4个正整数 $n,m,p, k( 1 \le n \le 200,1 \le m \le 200,0 \le p \le 50000, k \le 50000)$，分别代表甜点种类，箱子种类和参赛者比赛所需要补充的能量和小z所拥有的钱数。

接下来的n行，每行包含3个整数 $t_i, u_i, v_i ( 1 \le t_i \le 100,1 \le u_i \le 100,1 \le v_i \le 100)$ , 代表第 $i$ 类甜点可以提供 $t_i$ 的能量，它的大小为 $u_i$ 并且小明最多有 $v_i$ 个该种类的甜点。

接下来又有m行，每一行包含3个整数 $x_i, y_i, z_i ( 1 \le x_i \le 100,1 \le y_i \le 100,1 \le z_i \le 100)$, 代表第 $i$ 类箱子可以容纳 $x_i$大小的甜点，该类箱子的单价 $y_i$ ,并且小z最多可以使用 $z_i$ 个该类的箱子。

Output Format

第一行请输出最小的甜点大小。

第二行请输出最小的箱子费用，并且费用不能超过k。否则，输出FAIL。

Sample

样例输入1

5 3 34 34
1 4 1
9 4 2
5 3 3
1 3 3
5 3 2
3 4 5
6 7 5
5 3 8

样例输出1

19
12

Hint

对于 30%的数据: $n, m \le 15, p, k \le 1000$

对于 60%的数据: $n, m \le 50, p, k \le 5000$

对于100%的数据: $n, m \le 200, p \le 50000, k \le 50000$