Một ma trận N×N được đánh số từ 1 tới N2, theo các đường chéo hình zig-zag. Xem ví dụ dưới để hiểu rõ hơn cách đánh số: Với N=6:
|
1
|
2
|
6
|
7
|
15
|
16
|
|
3
|
5
|
8
|
14
|
17
|
26
|
|
4
|
9
|
13
|
18
|
25
|
27
|
|
10
|
12
|
19
|
24
|
28
|
33
|
|
11
|
20
|
23
|
29
|
32
|
34
|
|
21
|
22
|
30
|
31
|
35
|
36
|
Con thỏ ở trong ô số 1. Nó có thể nhảy sang các ô kề cạnh (trên, dưới, trái, phải) nếu ô đó tồn tại.
Cho K bước nhảy hợp lệ, viết chương trình tính tổng tất cả các số trên tất cả các ô mà thỏ ghé thăm (tức là mỗi bước đi qua 1 ô thì cộng số ở ô đó vào tổng).
Input
Dòng 1: 2 số nguyên cách nhau bởi dấu cách N và K (1 ≤N ≤ 100 000 , 1 ≤ K ≤ 300 000) lần lượt là kích thước của ma trận và số bước nhảy của con thỏ.
Dòng 2: Chứa dãy có K kí tự có thể là "U","D","L","R" tương ứng với các bước nhảy "lên","xuống","trái","phải". Các bước nhảy đảm bảo rằng sẽ không nhảy ra khỏi ma trận bất cứ lúc nào.
Output
Một số nguyên duy nhất là tổng của các ô mà con thỏ ghé thăm.
Lưu ý:
50% số test có N ≤ 1000
Example
Input:
6 8
DDRRUULL
Output:
47
Giải thích: Con thỏ ghé thăm các ô: 1, 3, 4, 9, 13, 8, 6, 2 và 1
Input:
3 8
DDRRUULL
Output:
41
Giải thích: Con thỏ ghé thăm các ô: 1, 3, 4, 8, 9, 7, 6, 2 và 1
Input:
6 10
RRRRRDDDDD
Output:
203
Giải thích: Con thỏ ghé thăm các ô: 1, 2, 6, 7, 15, 16, 26, 27, 33, 34 và 36.
