Bài tập

Viết chương trình nhập từ bàn phím một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, ..., a_n\). Tiếp theo, nhập vào hai số nguyên dương \(L\) và \(R\) \((1 \leq L \leq R \leq n)\). Hãy tính tổng các phần tử có chỉ số nằm trong đoạn \([L, R]\), hay cụ thể hơn là tính tổng \(a_{L} + a_{L + 1} + a_{L + 2} + ... + a_{R}\).

Input

• Dòng đầu tiên là số nguyên dương \(n\) - độ dài của dãy \(a\). \((1 \leq n \leq 100)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, a_3, ..., a_n\) - mỗi số cách nhau một dấu cách \((|a_i| \leq 100)\).
• Dòng thứ ba là hai số nguyên dương \(L\) và \(R\) \((1 \leq L \leq R \leq n)\).

Output

Yêu cầu bài toán.

Example

6
3 2 3 4 5 6
2 5

14

Cho một xâu \(s\) chỉ gồm các chữ cái thường Latin.
Mỗi ký tự trong xâu được đánh giá là tốt hoặc xấu.

Một xâu con liên tiếp của \(s\) được gọi là tốt nếu trong xâu con đó
có không quá \(K\) ký tự xấu.

Yêu cầu:
Hãy đếm số xâu con khác nhau của \(s\) mà là xâu con tốt.

**Lưu ý: hai xâu con là khác nhau khi nội dung của hai xâu là khác nhau, không quan trọng vị trí.

\InputFile

• Dòng đầu chứa xâu \(s\) \((|s| \le 1500)\).
• Dòng thứ hai chứa một xâu nhị phân \(b\) có độ dài \(26\),
  trong đó \(b_i = 1\) nếu ký tự thứ \(i\) trong bảng chữ cái là tốt,
  và \(b_i = 0\) nếu ký tự đó là xấu.
• Dòng thứ ba chứa số nguyên \(K\) \((0 \le K \le |s|)\).

\OutputFile
In ra một số nguyên duy nhất --- số lượng xâu con khác nhau của \(s\) mà là xâu con tốt.

Example

ababab
01000000000000000000000000
1

5

Cho \(n\) xâu \(S_1, S_2, \dots, S_n\).

Hãy tìm một xâu \(S\) có độ dài nhỏ nhất sao cho mọi \(S_1, S_2, \dots, S_n\) đều là xâu con liên tiếp của \(S\).
In ra độ dài của xâu \(S\) ngắn nhất đó.

\InputFile
Dòng đầu tiên gồm số nguyên \(n\).

\(n\) dòng tiếp theo, mỗi dòng gồm một xâu \(S_i\).

\OutputFile
In ra độ dài của xâu \(S\) ngắn nhất.

Điều kiện

• \(1 \le n \le 20\).
• \(1 \le |S_i| \le 100\).

Example

3
ab
bcc
da

5

Nhân dịp đầu năm mới, một cửa hàng đồ uống triển khai chương trình khuyến mãi đặc biệt dành cho khách hàng thân thiết. Nội dung của chương trình như sau: khi khách hàng mang đến cửa hàng \(10\) vỏ chai bia (cùng loại), họ sẽ được đổi lấy \(3\) chai bia mới miễn phí.

Anh Quân là một khách hàng đã mua ban đầu \(n\) chai bia. Sau khi uống hết, anh Quân muốn tận dụng chương trình khuyến mãi này để đổi vỏ chai lấy thêm bia. Anh Quân có thể tiếp tục uống và đổi vỏ chai mới nếu có, cho đến khi không thể đổi được nữa.

Yêu cầu: Hãy xác định tổng số chai bia tối đa mà anh Quân có thể uống được.

Input

Dữ liệu vào là một số nguyên dương \(n\) (\(1 \le n \le 10000\)) đại diện cho số chai bia anh Quân đã mua ban đầu.

Output

In ra một số nguyên duy nhất là tổng số chai bia tối đa mà anh Quân có thể uống được.

Example

16

19

10

13