RT，可以卡掉某些 AC 程序

虽然已经加强但仍然不够强啊

Input

8 20 1 3
1 3 8
7 3 8
4 2 3
8 2 4
7 5 3
1 8 4
8 8 3
6 7 8
2 5 3
5 3 7
7 8 6
1 4 7
2 4 2
1 5 8
4 6 2
8 4 2
7 2 8
8 8 1
6 5 4
1 3 4

Output

25