Trên một con đường có bố trí sẵn một số bóng đèn. Sơ đồ bố trí các bóng đèn trên con đường được biểu diễn bàng một xâu kí tự gồm kí tự chữ cái $D$ đại diện cho bóng đèn và giữa hai kí tự chữ cái $D$ có một vài kí tự chữ số biểu diễn cho một số nguyên dương là khoảng cách giữa hai bóng đèn này (đơn vị mét).

Yêu cầu: Xác dịnh khoảng cách (đơn vị mét) giữa bóng đèn đầu tiên và bóng đèn cuối cùng trên con đường.

Input

Nhập từ bàn phím một xâu kí tự biểu diễn sơ đồ bố trí bóng đèn.

Output

In ra màn hình một số nguyên $m$ theo yêu cầu.

Giới hạn

Xâu kí tự nhập từ bàn phim có không quá $255$ ki tự và số nguyên giữa $2$ kí tự $D$ không vượt quá $1000$.

Ví dụ

Sample input

D3D2D10D

Sample output

15

Giải thích ví dụ

Các khoảng cách lần lượt là $3,2,10$. Và tổng của chúng là $3+2+10=15$

Năm nay được mùa dưa, Tý theo bố mang rất nhiều quả dưa ra chợ bán. Có một ông thương gia đến chợ mua dưa, biết Tý là người thông minh, ông ta muốn đưa ra thừ thách cho Tý. Ông yêu cầu Tý thực hiện theo đúng trình tự sau:

• Bước 1: Tý phải chọn ra $N$ viên đá từ đống đá có sẵn ở chợ.
• Bước 2: Trong $N$ viên đá được chọn, loại ra những viên đá có khối lượng giống nhau.
• Bước 3: Ông ta sẽ mua những quả dưa có tổng khối lượng đúng bằng tổng khối lượng của những viên đá còn lại sau khi thực hiện bước $2$. Tý đã rất nhanh chóng thực hiện yêu cầu trên và bán được số dưa có tổng khối lượng lớn nhất.

Yêu cầu: Em hãy đưa ra cách Tý đã làm.

Input

Đọc từ file văn bản DUA.INP có cấu trúc như sau:

• Dòng thứ nhất chứa hai số nguyên $N$ và $K$ ($N\le K$), mỗi số cách nhau một dấu cách.
• Dòng thứ hai chứa $K$ số nguyên dương, mỗi số cách nhau một dấu cách. Mỗi số trong dăy số này biểu thị cho khối lượng cùa mỗi viên đá và mỗi số không vượt quá $10000$.
• Số lượng các viên đá có khối lượng nhỏ không ít hơn số lượng các viên đá có khối lượng lớn hơn.

Output

Ghi ra file văn bản DUA.OUT một số nguyên $m$ là khối lượng dưa lớn nhất mà bố cùa Tý có thể bán được.

Giới hạn

• $80$% số test có $K\le {10}^4$
• $20$% số test có ${10}^4<K\le {10}^5$

Ví dụ

Sample input

8 14
1 7 9 6 4 3 12 6 7 3 4 1 1 3

Sample output

41

Giải thích ví dụ

Tý chọn $8$ viên đá có khối lượng là $1;7;9;6;4;3;12;1$ sau đó bỏ đi $2$ viên có khối lượng bằng $1$ thì tống khối lượng còn lại là $41$.

Người ta viết liên tiếp các sổ chính phương $1^2;2^2;3^2;4^2;5^2;...;k^2$ thì được một số tự nhiên $X=149162536$...

Yêu cầu: Xác định số lượng chữ số của $X$.

Input

• Đọc từ file văn bản SCS.INP một số nguyên dương $k$.

Output

• Ghi ra file văn bản SCS.OUT số lượng chữ số của $X$ theo yêu cầu.

Giới hạn

• $30$% số lượng test ứng với $k\le {10}^6$
• $30$% số lượng test ứng với ${10}^6<k\le {10}^9$
• $30$% số lượng test ứng với ${10}^9<k\le {10}^{12}$

Ví dụ

Sample input

9

Sample output

15

Giải thích ví dụ

Với $k=9$ ta có $X=149162536496481$ là số có $15$ chữ số.

Bạn được cung cấp một mảng $n$ số nguyên. Nhiệm vụ của bạn là tính giá trị nhỏ nhất của từng đoạn $k$ phần tử, từ trái sang phải. (không hiểu thì xuống đọc giải thích ví dụ là hiểu)

Input

Dòng đầu tiên gồm 2 số nguyên $n$ và $k$ $(k\le n)$ Dòng tiếp theo chứa n số nguyên dương $a_1,a_2,\dots ,a_n$ $(a_i\le {10}^6)$

Output

In ra $n-k+1$ giá trị nhỏ nhất của $n-k+1$ đoạn, cách nhau bởi dấu cách

Giới hạn

• Subtask 1: $40$% số test có $n\le {10}^3$
• Subtask 2: $30$% số test có $n\ast k\le {10}^7$
• Subtask 3: $30$% số test có $n\le 5\ast {10}^5$

Ví dụ

Sample input

5 3
2 1 5 3 4 

Sample output

1 1 3

Giải thích ví dụ

• Giá trị nhỏ nhất của đoạn $(2,1,5)$ là $1$
• Giá trị nhỏ nhất của đoạn $(1,5,3)$ là $1$
• Giá trị nhỏ nhất của đoạn $(5,3,4)$ là $3$