题目描述 有一个n行m列的迷宫，左上角迷宫格的坐标为(1,1)，右下角迷宫格的坐标为(n,m)。 迷宫格中拥有障碍和价值不同的宝石。如果小猫走到有障碍的迷宫格则无法通过； 如果走到有宝石的迷宫格，

题目描述

有一个n行m列的迷宫，左上角迷宫格的坐标为(1,1)，右下角迷宫格的坐标为(n,m)。XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

迷宫格中拥有障碍和价值不同的宝石。如果小猫走到有障碍的迷宫格则无法通过；XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

如果走到有宝石的迷宫格，就会将宝石装进自己的袋子里。小猫从(1, 1)前往(n, m)，且只允许往下和往右走。XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

请为小猫选择一条获取宝石价值最高的路径，并输出宝石的总价值和小猫经过的路径。如果小猫无法到达(n,m)则输出-1。XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

第1行：n m p q，n、m分别表示迷宫的行和列 1<n、m<=10，p表示障碍的数量，q表示宝石的数量。 接下来的p行，每行2个整数，前一个整数表示障碍所在的行，后一个整数表示障碍所在的列。 解析来的q行，每行3个整数，前两个表示宝石所在的行和列，第3个整数表示宝石的价值。

输出

第1行：小猫搜集宝石的最大价值。 第2行：小猫所经过的路径。 如果小猫无法到达(n, m)则输出-1。 (遵从先右后下，找到的第一次结果为准)

数据范围

如果无特殊声明，则保证数据范围在整形范围以内

输入样例

3 4 4 8XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 3XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 4XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 1XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 3XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 1 1XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 2 5XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 1 1XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 2 2XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 3 1XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 4 1XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 2 8XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 4 5

输出样例

15XxR100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
(1,1)->(1,2)->(2,2)->(2,3)->(2,4)->(3,4)