34588번 - Explosive Slabstones Rearrangement 다국어

문제

Barbara has a garden. The garden can be represented as a $n \times m$ grid. She has placed $k$ slabstones in the garden, so she can enjoy stepping slabstones from one to another every day. The slabstones are indexed from 1ドル$ to $k$. Each slabstone fully occupies some cell of the garden, and no two slabstones are placed at the same cell.

However, an evil person, Babara, is going to place a special device that will occupy a rectangular region in the garden. If any slabstone overlaps with the device, it will explode and destroy the whole garden!

To avoid the explosion, Barbara wants to rearrange the slabstones by shifting the slabstones within the garden. The slabstones should remain non-overlapping during slabstone rearrangement. The energy spent is equal to the largest index among all slabstones that have been moved. Now Barbara wants to know the minimum energy required to rearrange the slabstones, so she can save her energy for “other purposes”.

For example, suppose the device will be placed at the blue rectangle. Then Barbara can rearrange the slabstones as follows. Please note that the slabstones do not overlap during the whole process, not only after the rearrangement. All slabstones that have been moved have index at most 4ドル,ドル so the energy spent is 4ドル$.

입력

The first line contains three integers $n,ドル $m$ and $k$.

Followed by $k$ lines, the $i$-th of which contains two integers $x_i$ and $y_i,ドル representing that the $i$-th slabstone is located at the $y_i$-th cell of the $x_i$-th row.

The last line contains four integers $u_1,ドル $v_1,ドル $u_2$ and $v_2,ドル representing that the top-left corner of the device is located at the $v_1$-th cell of the $u_1$-th row, and the bottom-right corner of the device is located at the $v_2$-th cell of the $u_2$-th row.

출력

Print the minimum energy required to rearrange the slabstones. If no slabstones need to be moved, the energy spent is 0ドル$. If the explosion cannot be avoided, just output $-1$.

제한

• 1ドル ≤ n ≤ 500$
• 1ドル ≤ m ≤ 500$
• 1ドル ≤ k ≤ n \times m$
• 1ドル ≤ x_i ≤ n$
• 1ドル ≤ y_i ≤ m$
• 1ドル ≤ u_1 ≤ u_2 ≤ n$
• 1ドル ≤ v_1 ≤ v_2 ≤ m$
• All $(x_i , y_i)$ pairs are distinct.

노트