Mushrooms
Masha is planning a visit to her grandmother and is bringing two baskets: one filled with pies and another empty, intended for collecting mushrooms along her journey.
To reach her grandmother's house, Masha must traverse a forest represented as an m×n grid. Some cells in this grid contain trees, while others have mushrooms. Masha begins her journey at cell (1, 1) and aims to reach her grandmother's village located at cell (m, n). She can move either right or down, meaning she can increase either her row or column coordinate by 1 with each move. However, she cannot move into a cell that contains a tree. If both the right and down cells are blocked by trees, Masha will be unable to proceed and is considered lost.
Your task is to determine whether Masha can successfully reach her grandmother without getting lost. If she can, you should also calculate the maximum number of mushrooms she can collect on her path.
Input
The first line of the input contains four integers: m, n, g, and t (2 ≤ m, n ≤ 100, 0 ≤ g, t ≤ g + t ≤ mn - 2). The following g lines each contain two numbers, representing the x and y-coordinates of each mushroom. After these, t lines follow, each describing the coordinates of a tree in the same format. No cell will contain more than one mushroom, nor will it contain both a mushroom and a tree, or more than one tree. Additionally, the starting cell (1, 1) and the destination cell (m, n) are free of any obstacles.
Output
If Masha can reach her grandmother, the first line of the output should display the maximum number of mushrooms she can collect. The subsequent m+n-1 lines should list the coordinates of the cells Masha visits in order, formatted as x[i]y[i], for the path that allows her to collect the maximum number of mushrooms. If there are multiple paths with the same maximum number of mushrooms, choose the path that prioritizes moving down.
If Masha cannot reach her grandmother, the output should be a single number -1.