很久以前，在遥远的国度住着一位好战的马尔纳（Malnar）皇帝。其他王国联合起来对抗他，并率领一支庞大的军队进攻他的城堡。

通往城堡的唯一路径是一条长长的道路，沿途设有 $n$ 座塔。在这条路上，第 $i$ 座塔的视野范围是区间 $[l_i, r_i]$，塔上有 $p_i$ 名弓箭手。每名弓箭手每秒可以射中一名士兵。

一支由 $k$ 名士兵组成的庞大军队正沿着这条路行进。军队每秒移动一米。例如，如果军队经过一个监控范围为 $2$ 到 $5$ 的塔，且塔上有 $1$ 名弓箭手，那么在军队走出该塔的视野范围之前，这名弓箭手将射中 $3$ 名士兵。每座塔附近都有一个村庄。第 $i$ 个村庄有 $s_i$ 名村民愿意提供帮助，他们可以全部加入第 $i$ 座塔成为弓箭手，费用为 $c_i$ 枚金币。马尔纳皇帝虽然贪婪但很大方，他希望花费尽可能少的金币来击败敌军。请帮助他！

输入格式

第一行包含两个自然数 $n$ ($1 \le n \le 1\,000$) 和 $k$ ($1 \le k \le 10\,000$)。

接下来的 $n$ 行，每行包含三个自然数 $l_i, r_i, p_i$ ($1 \le l_i, r_i, p_i \le 1\,000, l_i < r_i$)，依次表示第 $i$ 座塔的视野范围左边界、右边界以及塔上现有的弓箭手数量。塔的区间可能会重叠。

接下来的 $n$ 行，每行包含两个自然数 $s_i, c_i$ ($1 \le s_i \le 1\,000, 1 \le c_i \le 10^5$)，表示第 $i$ 座塔可以通过支付 $c_i$ 枚金币获得 $s_i$ 名额外弓箭手的支援。

输出格式

输出一行，表示击败敌军所需的最少金币数量。如果无论如何都无法击败敌军，请输出 "PREDAJA"。

样例

样例输入 1

3 17
1 4 2
3 5 3
5 7 1
4 10
1 3
2 6

样例输出 1

6

样例输入 2

2 20
1 2 1
2 4 2
4 14
3 20

样例输出 2

PREDAJA