Farmer John khá đáng tin cậy trong mọi khía cạnh quản lý trang trại, ngoại trừ một điều: ông cực kỳ tệ trong việc cắt cỏ đúng lúc hoặc theo một trình tự hợp lý.

Trang trại là một lưới hai chiều lớn gồm các ô vuông đơn vị. FJ bắt đầu tại một trong các ô này vào thời điểm \(t=0\) và cắt cỏ trong ô đó, vì vậy ban đầu đây là ô duy nhất có cỏ đã được cắt. Lộ trình cắt cỏ còn lại của FJ được mô tả bằng một dãy \(N\) chỉ dẫn. Chẳng hạn, nếu chỉ dẫn đầu tiên là W 10, thì từ thời điểm \(t=1\) đến \(t=10\) (tức 10 đơn vị thời gian tiếp theo), ở mỗi thời điểm FJ bước sang ô liền kề phía tây và cắt cỏ trên đường đi. Sau khi hoàn thành dãy bước này, vào thời điểm \(t=10\), ông sẽ ở cách vị trí ban đầu 10 ô về phía tây và đã cắt cỏ trong mọi ô trên đường đi.

FJ tiến triển chậm đến mức một phần cỏ ông đã cắt có thể mọc lại trước khi ông hoàn tất toàn bộ công việc. Bất kỳ phần cỏ nào được cắt tại thời điểm \(t\) sẽ mọc lại vào thời điểm \(t+x\).

Lộ trình cắt cỏ có thể khiến FJ ghé lại cùng một ô nhiều lần, nhưng ông nhận xét rằng mình không bao giờ gặp một ô mà cỏ vẫn chưa mọc lại sau lần cắt trước. Nói cách khác, mỗi khi ông ghé một ô, lần gần nhất ông từng ghé chính ô đó phải cách ít nhất \(x\) đơn vị thời gian để cỏ kịp mọc lại.

Hãy xác định giá trị lớn nhất có thể của \(x\) sao cho nhận xét của FJ vẫn đúng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1\le N\le100\)). Mỗi dòng trong \(N\) dòng còn lại chứa một chỉ dẫn có dạng D S, trong đó D là một ký tự mô tả hướng (N = bắc, E = đông, S = nam, W = tây) và S là số bước đi theo hướng đó (\(1\le S\le10\)).

Dữ liệu ra

In giá trị lớn nhất của \(x\) sao cho FJ không bao giờ bước vào một ô có cỏ vẫn chưa mọc lại sau lần cắt trước. Nếu FJ không bao giờ ghé bất kỳ ô nào quá một lần, hãy in -1.

Ví dụ

6
N 10
E 2
S 3
W 4
S 5
E 8

10

Nguồn

USACO 2016 January Contest, Bronze - Mowing the Field: https://usaco.org/index.php?page=viewproblem2&cpid=593

Tác giả: Brian Dean.