영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
You are soon going to sell your house, but first, you need to figure out the size of the floor area. It might sound easy, but you have an unused storage room for which you've lost the key, and you have no idea how big the storage room is. The only thing in the storage room is a robot vacuum cleaner. If you start the vacuum cleaner and see where it ends up, maybe you can figure out how big the storage room is?
The storage room consists of an N × M grid, where N and M are unknown positive integers. The rows are numbered from 0 to N-1 from top to bottom, and the columns are numbered from 0 to M-1 from left to right. The robot has a list of instructions s. The instructions are described by a string consisting of the characters <, >, ^, and v. When the robot is started, it reads these instructions, and for each one, it moves one step in the corresponding direction. If the robot tries to move outside the grid, then it hits a wall and nothing happens. The robot starts in the upper-left corner, i.e., at row 0 and column 0.
You are given the string s and the row and column where the robot ended up after following the instructions. Calculate the smallest possible value of N · M that is consistent with this information.
Input
The first line contains an integer K (1 ≤ K ≤ 3 · 10^5), the length of the string s.
The second line contains the string s.
The third line contains two integers r and c (0 ≤ r,c < 3 · 10^5), where r is the row where the robot ended up, and c is the column where it ended up.
Output
Print an integer, the smallest possible value of N · M. If there is no choice of N and M consistent with the information in the test data, then print -1 instead.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 15 | The robot only moves down and to the right. |
| 2 | 30 | K ≤ 100 |
| 3 | 20 | K ≤ 5000 |
| 4 | 35 | No additional constraints. |
Explanation of sample case
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The picture shows the smallest possible grid in sample case 1. The robot travels according to the black curve. The dark square is the robot's final position.
예제
예제 1
14 >v<v>v>^^^>>v< 1 2
8
예제 2
1 > 100000 100000
-1
예제 3
4 >><< 0 0
1