Once upon a time in a distant land lived Emperor Malnar, who loved to wage war. The other kingdoms united against him and set out to attack his castle with a large army.

The only path to the castle is a long trail, along which $n$ towers are placed. On this path, the $i$-th tower covers the interval from $l_i$ to $r_i$ and has $p_i$ archers. Each archer can hit one soldier per second.

A large army consisting of $k$ soldiers travels along the path. The army moves at a speed of one meter per second. For example, if the army encounters a tower that covers the area from $2$ to $5$ and has one archer, that archer will hit $3$ soldiers before the army leaves the tower's field of vision. Near each tower, there is a village. In the $i$-th village, there are $s_i$ peasants who are willing to help and all together become archers for the $i$-th tower for $c_i$ gold coins. Emperor Malnar is greedy and generous, and he wants to spend as little gold as possible to defeat the enemy army. Help him!

Input

The first line contains the natural numbers $n$ ($1 \le n \le 1\,000$) and $k$ ($1 \le k \le 10\,000$) from the problem description.

The next $n$ lines contain the natural numbers $l_i, r_i, p_i$ ($1 \le l_i, r_i, p_i \le 1\,000, l_i < r_i$), which represent the left and right boundaries of the $i$-th tower's field of vision, and the number of archers at the $i$-th tower, respectively. The intervals of the towers may overlap.

The next $n$ lines contain the natural numbers $s_i, c_i$ ($1 \le s_i \le 1\,000, 1 \le c_i \le 10^5$), which indicate that $s_i$ peasants can help the $i$-th tower for $c_i$ gold coins.

Output

In the first and only line, print the minimum amount of gold required to defeat the enemy army. If it is impossible to defeat the army, print "PREDAJA".

Examples

Input 1

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

Output 1

6

Input 2

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

Output 2

PREDAJA