Để dễ dàng quản lý hiệu sách, Tý đã đánh số hiệu cho các quyển sách trong hiệu sách của mình. Theo đó, các quyển sách cùng loại được đánh cùng một số hiệu là một số nguyên dương và phân biệt với số hiệu của các loại sách khác. Sau một thời gian kinh doanh, hiệu sách của Tý còn lại ~N~ quyển sách có số hiệu tương ứng là ~a_1, a_2, ... a_N~.

Yêu cầu: Hãy viết chương trình giúp Tý tìm ra một loại sách đang còn nhiều nhất trong cửa hiệu và đưa ra số lượng quyển sách loại đó.

Input

Vào từ file văn bản DEMSACH.INP:

• Dòng thứ nhất: Ghi số nguyên dương ~N~ (~1 \leq N \leq 10^6~) là số lượng sách còn trong cửa hiệu.
• Dòng thứ hai: Ghi ~N~ số nguyên dương ~a_1,a_2,...,a_N~ (~1 \leq i \leq N, 1 \leq a_i \leq 10^6~).

Output

Vào từ file văn bản DEMSACH.OUT một số nguyên dương ~t~ là số lượng của 1 loại sách còn nhiều nhất trong hiệu sách.

Example input 1

10
2 1 2 6 2 4 5 2 6 7

Example output 1

4

Theo quan niệm dân gian, trong các biển số xe, biển số đẹp là biển số mà tổng các chữ số trên biển cộng lại và chia lấy dư cho ~10~ thì đúng bằng ~9~. Ví dụ: Biển số xe có số ~7309~ là biển số đẹp vì ~(9 +7 + 0 + 3)~ ~mod~ ~10~ ~=~ ~9~. Cho ~N~ biển số xe có các số tương ứng là ~a_1, a_2, ... a_N~.

Yêu cầu: Kiểm tra xem có bao nhiêu biển số đẹp trong ~N~ biển số trên.

Input

Vào từ file văn bản BIENSO.INP:

• Dòng thứ nhất ghi số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng thứ hai ghi ~N~ số nguyên dương ~a_1,a_2,...,a_N~ (~1 \leq i \leq N, 1 \leq a_i \leq 10^9~).

Output

Vào từ file văn bản BIENSO.OUT một số nguyên dương ~t~ là số lượng biển số đẹp tìm được.

Example input 1

4
2245 54712 33423  10981

Example output 1

2

Mật khẩu là một xâu ký tự. Một mật khẩu được gọi là ~an~ ~toàn~ nếu thỏa mãn tất cả các điều kiện sau:

• Số lượng ký tự trong xâu (độ dài của xâu) phải lớn hơn hoặc bằng ~6~.
• Chứa ít nhất một ký tự chữ cái in hoa trong đoạn ~['A'.. 'Z']~.
• Chứa ít nhất một ký tự chữ cái in thường trong đoạn ~['a'.. 'z']~.
• Chứa ít nhất một ký tự chữ số trong đoạn ~['0'.. '9']~.

Cho một xâu ký tự ~S~ có độ dài không quá ~10^5~.

Yêu cầu: Kiểm tra xem có bao nhiêu xâu con gồm các ký tự liên tiếp nhau trong xâu ~S~ có thể chọn làm mật khẩu ~an~ ~toàn~.

Input

Vào từ file văn bản MATKHAU.INP chỉ gồm một xâu ký tự ~S~.

Output

Vào từ file văn bản MATKHAU.OUT một số nguyên dương ~t~ là kết quả tìm được theo yêu cầu.

Example input 1

ABC123abc

Example output 1

8

Example input 2

ABC123

Example output 2

0

Nhân dịp chào mừng kỷ niệm ngày thành lập Quân đội Nhân dân Việt Nam, Liên đội đã lên kế hoạch tổ chức Hội thi kéo co giữa các lớp trong toàn trường. Theo quy định của Ban tổ chức, số lượng thành viên của mỗi đội thi là không hạn chế và tổng cân nặng của các thành viên tham gia mỗi đội không vượt quá ~K~ kilogam. Là lớp trưởng lớp ~9A~, Tý cũng rất háo hức để chuẩn bị cho đội thi của lớp mình nên đã tìm hiểu rất kỹ về Hội thi. Sau khi tham khảo kinh nghiệm từ các thầy cô, cậu biết được rằng đội nào có tổng chiều cao các thành viên lớn nhất thì thường là đội vô địch. Do đó, Tý cũng rất muốn chọn ra đội thi của lớp mình sao cho tổng chiều cao các thành viên trong đội là lớn nhất.
Lớp của Tý có ~N~ học sinh được đánh số từ 1 đến N. Cân nặng tương ứng của các thành viên là ~a_1, a_2, ..., a_N~ và chiều cao tương ứng của các thành viên là ~b_1, b_2, ..., b_N~. Yêu cầu: Hãy lập trình giúp Tý chọn được các thành viên của đội sao cho tổng chiều cao của đội là lớn nhất mà vẫn đảm bảo quy định của Ban tổ chức.

Input

Vào từ file văn bản KEOCO.INP:

• Dòng thứ nhất: Ghi ~2~ số nguyên dương ~N,K~ (~1 \leq N \leq 150,1 \leq K \leq 10^9~).
• Dòng thứ hai: Ghi ~N~ số nguyên dương ~a_1,a_2,...,a_N~ (~1 \leq i \leq N, 1 \leq a_i \leq 10^9~).
• Dòng thứ ba: Ghi ~N~ số nguyên dương ~b_1,b_2,...,b_N~ (~1 \leq i \leq N, 1 \leq b_i \leq 10^9~).

Output

Vào từ file văn bản KEOCO.OUT ghi một số nguyên dương ~t~ duy nhất là tổng chiều cao lớn nhất có thể của đội thi.

Scoring

• Subtask ~1~ ~(70\%)~: ~1 \leq N \leq 100, 10^5 \leq K \leq 10^9~.
• Subtask ~1~ ~(30\%)~: ~100 < N \leq 150, 1 \leq K \leq 10^4~.

Example input 1

5 140 
44 50 30 35 46
130 150 120 150 140

Example output 1

440