Trong lớp, năm người bạn thân Lan, Mai, Cúc, Hồng, Huệ được các bạn trong lớp đặt biệt danh là nhóm Ngũ Long Công Chúa. Tuần sau là sinh nhật của Lan, các bạn trong lớp phân công cho Mai lo việc đặt bánh sinh nhật. Để tạo sự mới lạ, Mai nghĩ ra ý tưởng là sẽ sử dụng những ngọn nến có hình dạng chữ cái và con số để khi thắp nến sẽ tạo thành một dòng chữ lung linh xung quanh bánh. Cô chủ tiệm bánh cho biết giá của mỗi ngọn nến có dạng chữ cái in hoa và chữ số là 3, chữ cái in thường là 2. Hãy tính tổng số tiền mà Mai và các bạn cần bỏ ra để mua các ngọn nến.

Dữ liệu vào

Một dòng ghi xâu S có ít nhất 1 ký tự, tối đa không quá 1000 ký tự, trong đó các ký tự có thể là chữ cái in hoa, in thường hoặc chữ số, không có khoảng trắng.

Dữ liệu ra

Một số nguyên duy nhất là số tiền cần bỏ ra để mua nến.

Ví dụ

DATBANH.INP

Lan1988

DATBANH.OUT

19

Ràng buộc

• 60% số test có độ dài xâu S không quá 200 ký tự;
• 40% số test còn lại không ràng buộc gì thêm.

Hôm nay bốn bạn Mai, Cúc, Hồng, Huệ sẽ cùng nhau đi mua quà để dự sinh nhật của Lan vào ngày mai. Trong cửa tiệm quà lưu niệm có n phần quà thuộc nhiều loại quà khác nhau, trong đó có những loại quà chỉ còn duy nhất một phần. Hồng biết rằng sáng mai các bạn trong lớp cũng sẽ đến đây mua quà, nên Hồng muốn quà của nhóm mình phải khác biệt hoàn toàn với quà của các bạn khác. Cô chủ tiệm hiểu ý và đã vui vẻ lấy ra những loại quà chỉ còn duy nhất một phần để Hồng và các bạn cùng lựa chọn.

Yêu cầu: Em hãy cho biết trong cửa tiệm có bao nhiều phần quà đáp ứng được yêu cầu của Hồng và các bạn.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương n (n ≤ ~10^5~);
• Dòng tiếp theo ghi n số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| ≤ 10^6~), những số giống nhau là cùng một loại quà.

  Dữ liệu ra:

Một số nguyên duy nhất là số lượng loại quà đáp ứng được yêu cầu của Hồng và các bạn.

Ví dụ:

MUAQUA.INP

5
2 1 2 3 1   

MUAQUA.OUT

1

Ràng buộc:

• 40% số test có n ≤ 200;
• 60% số test còn lại không ràng buộc gì thêm.

Tối nay sẽ là sinh nhật Lan. Nhóm bạn thân Mai, Cúc, Hồng, Huệ sẽ đi đến tiệm trang điểm để làm đẹp. Trên menu lựa chọn của tiệm có n kiểu trang điểm khác nhau, được đánh thứ tự từ kiểu 1 đến kiểu n, mỗi kiểu trang điểm sẽ có độ ấn tượng lần lượt là ~a_1, a_2, ..., a_n~, độ ấn tượng của mỗi kiểu là duy nhất, không có hai kiểu nào có cùng độ ấn tượng với nhau. Đương nhiên là mỗi bạn đều muốn mình là người ấn tượng nhất trong buổi tiệc, nhưng là nhóm bạn thân nên không thể để một người ấn tượng hơn người khác trong nhóm quá nhiều. Các bạn quyết định sẽ chọn mỗi người một kiểu trang điểm sao cho với cách chọn đó thì độ ấn tượng của từng người trong nhóm chênh lệch nhau là nhỏ nhất, và đương nhiên khi có nhiều sự lựa chọn thì sẽ chọn cách có độ ấn tượng càng cao càng tốt.

Yêu cầu: Em hãy xác định độ chênh lệch ấn tượng lớn nhất giữa 4 kiểu mà các bạn lựa chọn và cho biết đó là 4 kiểu trang điểm nào.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương n (n ≤ ~10^5~);
• Dòng tiếp theo ghi n số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i ≤ 10^6~) khác nhau đôi một.

Dữ liệu ra:

• Dòng đầu ghi độ chêch lệch ấn tượng lớn nhất giữa 4 kiểu trang điểm thỏa mãn yêu cầu của các bạn.
• Dòng tiếp theo ghi 4 số nguyên theo thứ tự trong menu của 4 kiểu được chọn, ghi theo thứ tự tăng dần, mỗi số cách nhau một khoảng trắng.

Ví dụ:

LAMDEP.INP

6
3 4 7 5 10 8
2 3 4 6 

LAMDEP.OUT

4

GIẢI THÍCH

Chọn kiểu trang điểm thứ 2, 3, 4, 6 có độ ấn tượng lần lượt là 4, 7, 5, 8, có độ chêch lệch lớn nhất giữa 2 kiểu là 4

Ràng buộc:

• 30% số test có n ≤ 50;
• 30% số test với các kiểu trang điểm trên menu có độ ấn tượng tăng hoặc giảm dần;
• 40% số test còn lại không ràng buộc gì thêm.

Buổi tiệc sinh nhật của Lan đã bắt đầu. Phần sinh động nhất trong cả đêm nay là các bạn trong lớp sẽ lần lượt trình bày các tiết mục văn nghệ để tặng Lan. Tuần trước, Huệ đã được phân công chuẩn bị bài hát cho cả lớp, tuy nhiên do máy tính gặp sự cố nên hiện giờ cô chỉ chuẩn bị được k bài hát, không đủ để từng bạn hát đơn ca được. Các bạn quyết định sẽ sử dụng phương án hát tốp ca để đảm bảo ai cũng sẽ được hát. Nhưng do chất giọng mỗi người khác nhau, nên những bạn có chất giọng tương đồng sẽ được phân chia vào một nhóm.

Sau khi phân chia lần đầu, có tất cả n nhóm, mỗi nhóm có số lượng thành viên lần lượt là ~a_1, a_2, ..., a_n~. Lúc này, nếu số lượng nhóm ít hơn so với số lượng bài hát thì những nhóm có quá nhiều thành viên có thể tiếp tục chia ra thành nhiều nhóm nhỏ hơn, sao cho số lượng thành viên trong mỗi nhóm là ít nhất có thể.

Ví dụ một nhóm có 4 người có thể chia ra thành 2 nhóm (mỗi nhóm 2 người hoặc một nhóm 3 người và một nhóm 1 người) hoặc 3 nhóm (2, 1, 1) hoặc 4 nhóm (1, 1, 1, 1). Những bạn có chất giọng không tương đồng nhau thì không thể hát cùng với nhau, tức là sẽ có những nhóm chỉ có 1 bạn. Sau một lúc phân chia, cuối cùng số lượng nhóm đúng bằng k và đảm bảo buổi tiệc diễn ra đúng như kế hoạch.

Yêu cầu: Hãy cho biết nhóm có nhiều thành viên nhất là bao nhiêu người.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương n và k (n ≤ ~10^5~, k ≤ ~10^6~), lần lượt là số lượng nhóm sau khi phân chia lần đầu và số bài hát đã chuẩn bị.
• Dòng tiếp theo ghi n số nguyên dương ~a_i~ (~a_i ≤ 10^4~), là số lượng thành viên hiện tại của nhóm thứ i sau khi phân chia.

  Dữ liệu ra:

Gồm một dòng ghi số lượng thành viên của nhóm có nhiều thành viên nhất sau khi phân chia lần thứ 2.

Ví dụ:

TOPCA.INP

4 8
5 1 7 3 

TOPCA.OUT

3

GIẢI THÍCH

Có thể chia 7 thành bốn nhóm là 2, 2, 2, 1 và 5 thành hai nhóm là 2, 3, vậy nhóm có nhiều thành viên nhất là 3.

Ràng buộc:

• 50% số test có n ≤1000, ~a_i~ ≤ 100;
• 50% số test còn lại không ràng buộc gì thêm.