A21282.遥远的牧场

给出一个n*n的括号矩阵，从一个点走到相邻的同字符点需付出A的代价，到不同字符点需付出B的代价。求所有点对之间最短路的最大值。

• 第 1 行：三个整数：N （1 <= N <= 30）、A （0 <= A <= 1,000,000） 和 B （0 <= B <= 1,000,000）。

• 第 1..N+1 行：每行包含一串长度为 N 的括号，这些 N 行共同形成一个 N x N 网格括弧。

• 第 1 行：一个整数，指定 Bessie 可以在一对牧场之间旅行的最大时间（假设她总是遵循花费最少时间的路线）。

Bessie 需要 5 个单位的时间才能在网格的左上角和右下角之间移动。没有其他牧场能比这更能让她旅行更长的时间。