"Các bài tập trên địa hình khác nhau rất quan trọng để tạo nên một đấu sĩ xuất sắc."

Sau khi xuống dưới hang thăm người bạn thân của mình, Fanmu, Piccôlô cần phải tìm cách nhanh nhất để sử dụng chiêu thức của mình, trèo lại lên trên mặt đất, trước khi bị bầy quỷ tìm đến và có ý định ám sát.

Để làm được điều này, hắn ta phải sử dụng những tấm ván, đã được lắp sẵn vuông góc với hai bức tường thẳng đứng. Hai bức tường này song song với nhau, cách nhau ~W~ cm, và vuông góc với mặt đất. Với mỗi tấm ván có chỉ số ~i~, hắn ta biết ba thông tin:

1. Được lắp vuông góc với bức tường trái, hay phải ('L' hay 'R').

2. Có độ dài là ~a_i~ (cm) (~a_i \le \lfloor\frac{W}{2}\rfloor~), tức là điểm xa nhất trên tấm ván sẽ cách bức tường nó được lắp lên là độ dài này.

3. Có độ cao là ~h_i~ (cm) so với đáy hang.

Piccôlô đang đứng sẵn ở trên tấm ván đầu tiên. Ở bất kỳ thời điểm nào, hắn ta có thể nhảy lên một tấm ván khác cao hơn nếu những điều kiện sau thỏa mãn:

• Tấm ván đó được lắp đặt lên bức tường phía đối diện.

• Bạn có thể vẽ một đoạn thẳng từ một điểm bất kỳ trên tấm ván đang đứng, đến điểm xa nhất (so với bức tường mà nó được gắn lên) trên tấm ván mục tiêu, mà không bị cản trở bởi bất kỳ tấm ván nào khác.

Để ra được khỏi hang, Piccôlô cần phải đáp được lên tấm ván cao nhất trên hành trình. Hãy in ra số bước ít nhất Piccôlô cần để làm được điều này. Nếu tấm ván cao nhất không thể đáp tới được với mọi cách đi, in ra -1.

Input

Dòng đầu chứa hai số nguyên: ~N~ và ~W~ (~2 \le N \le 3000~, ~2 \le W \le 10^9~) - thể hiện số tấm ván Piccôlô có thể sử dụng, và khoảng cách giữa hai bức tường.

Dòng thứ hai chứa ~N~ số nguyên: ~h_1, h_2, \ldots, h_N~ (~1 \le h_1 < h_2 < \ldots < h_N \le 10^9~), thể hiện độ cao của từng tấm ván.

Dòng thứ ba chứa ~N~ số nguyên: ~a_1, a_2, \ldots, a_n~ (~1 \le a_1, a_2, \ldots, a_N \le \lfloor\frac{W}{2}\rfloor~), thể hiện độ dài của từng tấm ván.

Dòng thứ tư chứa ~N~ ký tự, cách nhau bởi các dấu cách. Ký tự thứ ~i~ (~1 \le i \le N~) có thể là 'L' hoặc 'R', thể hiện bức tường mà tấm ván thứ ~i~ được lắp lên.

Output

In ra -1 nếu Piccôlô không thể nhảy lên tấm ván cao nhất, tức là tấm ván thứ ~N~.

Ngược lại, in ra số bước ít nhất Piccôlô có thể nhảy để thoát khỏi hang.

Sample Input 1

3 2
1 2 3
1 1 1
L R L

Sample Output 1

2

Sample Input 2

7 7
1 3 4 5 6 7 9
1 1 3 2 3 3 2
R L R L L R L

Sample Output 2

3

Sample Input 3

3 20
1 2 3
10 9 1
L R R

Sample Output 3

1

Notes

Đối với test ví dụ đầu tiên, Piccôlô cần nhảy hai lần như trong hình dưới đây:

Đối với test ví dụ thứ hai, Piccôlô cần nhảy ba lần lên các tấm ván thứ 2, 3 và 7 như trong hình dưới đây. Ngoài ra, Piccôlô cũng có thể nhảy lên tấm ván thứ 4 từ lần nhảy đầu tiên, nhưng sau đó không thể nhảy lên tấm ván thứ 6 vì bị chặn lại bởi tấm ván thứ 5.