Bé Bo nhận được một mảnh giấy trên đó có ghi một đoạn ký tự chỉ có các ký tự latin in thường ('a'..'z').

Yêu cầu: Bạn hãy cho biết trong xâu ký tự Bé Bo nhận được có bao nhiêu lần xuất hiện đoạn ký tự 'virus'.

Input

Gồm một xâu kí tự có độ dài không quá ~250~ kí tự.

Output

Một số nguyên duy nhất là số lần xuất hiện xâu 'virus' trong xâu ký tự đã cho.

Sample Input 1

hpvirushnviruss

Sample Output 1

2

Bé Bo được bố mua cho ~n~ tấm bìa đánh số từ ~1~ đến ~n~, trên tấm bìa ~i~ ~(1 \le i \le n)~ có ghi một số nguyên dương ~a_i~ (~1 \le a_i \le 99~). Bo đặt ngẫu nhiên ~n~ tấm bìa thành một hàng ngang trên bàn và ghi lại các số trên các tấm bìa theo thứ tự từ trái qua phải.

Ví dụ: Bé Bo có ~3~ tấm bìa ghi các số ~3, 7, 5~. Khi xếp ngẫu nhiên thành một hàng ngang và ghi các số theo thứ tự thì có thể thu được ~6~ số nguyên dương là ~357, 375, 537, 573, 735, 753~. Số lớn nhất có thể tạo thành là ~753~.

Input

Dòng thứ nhất chứa một số nguyên dương ~n~.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i~ ~(1 \le i \le n)~.

Output

Ghi ra một số nguyên duy nhất là số lớn nhất tìm được.

Scoring

Sample Input 1

3
20 21 22

Sample Output 1

222120

Sample Input 2

3
2 21 22

Sample Output 2

22221

Trang trại gà của nhà Bé Bo có ~n~ con gà siêu trứng đánh số từ ~1~ đến ~n~. Con gà ~i~ ~(1 \le i \le n)~ đẻ quả trứng đầu tiên ở giây ~p_i~, sau đó cứ ~t_i~ giây tiếp theo sẽ đẻ thêm một quả trứng.

Yêu cầu: Bạn hãy viết chương trình tính thời gian nhỏ nhất (tính bằng giây) để Bé Bo thu được ít nhất ~x~ quả trứng.

Input

- Dòng thứ nhất chứa hai số nguyên dương ~n, x~;

- ~n~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le n)~ chứa hai số nguyên dương ~p_i~, ~t_i~ (~1 \le p_i, t_i \le 500~).

Output

Ghi ra một số nguyên duy nhất là thời gian nhỏ nhất để Bé Bo thu được ít nhất ~x~ quả trứng.

Scoring

Scoring table:

Sample Input 1

2 3
10 30
5 25

Sample Output 1

30

Sample Input 2

2 3
10 5
5 10

Sample Output 2

15

Notes

Ở ví dụ đầu tiên:

Con gà số ~1~ đẻ quả trứng đầu tiên ở giây ~10~, đẻ quả trứng thứ ~2~ ở giây ~40~, quả trứng thứ ~3~ ở giây ~70~, ...

Con gà số ~2~ đẻ quả trứng đầu tiên ở giây ~5~, đẻ quả trứng thứ ~2~ ở giây ~30~, quả trứng thứ ~3~ ở giây ~55~, ...

Vậy chỉ sau ~30~ giây thì tổng số trứng thu được là ~3~ quả.

Ở ví dụ thứ hai:

Con gà số ~1~ đẻ quả trứng đầu tiên ở giây ~10~, đẻ quả trứng thứ ~2~ ở giây ~15~, ...

Con gà số ~2~ đẻ quả trứng đầu tiên ở giây ~5~, đẻ quả trứng thứ ~2~ ở giây ~15~, ...

Vậy:

Tổng số trứng thu được sau ~5~ giây: ~1~

Tổng số trứng thu được sau ~10~ giây: ~2~

Tổng số trứng thu được sau ~15~ giây: ~4~