Trường mới đẹp và rộng hơn trường cũ. Số phòng học cũng nhiều hơn 2 so với trước. Nhà trường dự định tuyển thêm học sinh cho ~2~ lớp mới, với số học sinh ở hai lớp lần lượt là ~x~ và ~y~. Dĩ nhiên, cần mua bộ bàn ghế cho hai lớp này; giá mỗi bộ bàn ghế là ~z~ đồng. Mỗi bộ bàn ghế chỉ chứa tối đa ~2~ học sinh.

Yêu cầu: Hãy xác định số lượng bộ bàn ghế cần mua và tổng kinh phí tối thiểu để trang bị cho hai phòng học mới.

Input

Gồm một dòng duy nhất ~3~ số nguyên ~x~, ~y~, ~z~ ~(1 \le x, y \le 50, 1 \le z \le 10^4)~

Output

Dòng đầu tiên in ra một số nguyên là số lượng bộ bàn ghế cần mua.

Dòng cuối cùng in ra một số nguyên là tổng chi phí tối thiểu.

Sample Input

20 21 200

Sample Output

21
4200

Trên một bảng điện tử có gắn các bóng đèn hiển thị màu. Mỗi bóng được gắn một mã điều khiển là một số nguyên dương theo thứ tự từ ~1~ đến ~n~. Dãy bóng có mã từ ~a~ đến ~b~ ~(a < b)~ đang được hiển thị: Các bóng đèn có mã là một số chẵn hiển thị màu xanh, mã số lẻ được hiển thị màu đỏ, đặc biệt các bóng có mã chia hết cho ~3~ hiển thị màu vàng.

Giả sử dãy bóng có mã từ ~a=2~ đến ~b=10~ thì: Các bóng hiển thị màu xanh có mã ~2, 4, 8, 10~; Các bóng hiển thị màu đỏ có mã ~1, 5, 7~; Các bóng hiển thị màu vàng có mã ~3, 6, 9~.

Yêu cầu: Cho biết hai số nguyên a và b. Hãy tìm số lượng bóng đèn đang hiển thị màu xanh ?

Input

Gồm một dòng duy nhất chứa ~2~ số nguyên ~a, b~ ~(1 \le a \le b < 10^{18})~

Output

Gồm một số nguyên duy nhất là số lượng bóng đèn đang hiển thị màu xanh.

Sample Input 1

2 10

Sample Output 1

4

Sample Input 2

10 15

Sample Output 2

2

Subtask

• Subtask 1: Có ~80\%~ số điểm tương ứng ~80\%~ số test với ~1 \le a \le b \le 10^9~

• Subtask 2: Có ~20\%~ số điểm tương ứng ~20\%~ số test với ~10^9 < a \le b < 10^{18}~

Một bộ ba số được gọi là bộ số tam giác, nếu ba số này là độ dài ba cạnh của một tam giác. Cho dãy số ~4, 3, 1, 5, 7~, ta có 3 bộ số tam giác là ~(3, 4, 5)~, ~(3, 5, 7)~ và ~(4, 5, 7)~.

Cho dãy số gồm n số nguyên dương ~a_1, a_2, ..., a_n (1 ≤ i ≤ n)~.

Yêu cầu: Hãy đếm xem trong dãy ~a~ có bao nhiêu bộ số tam giác ~(a_i, a_j, a_k)~ với ~i, j, k~ đôi một khác nhau.

Input

Dòng đầu chứa số nguyên dương ~n~ ~(3 \le n \le 1000)~;

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n (a_i \le 10^9)~.

Output

In ra một số nguyên duy nhất là số lượng bộ số tam giác trong dãy ~a~.

Sample Input

5
4 3 1 5 7

Sample Output

3

Subtask

• Subtask 1: Có ~60\%~ số điểm tương ứng ~60\%~ số test với ~n \le 500~.

• Subtask 2: Có ~40\%~ số điểm tương ứng ~40\%~ số test với ~n \le 1000~.

Trong tiết học thủ công ở trường, Tèo được cô giáo hướng dẫn vẽ cách lắp ghép các hình: hình vuông, hình tam giác, hình chữ nhật... Để tăng độ khó và ghi nhớ kiến thức đã học, Tí – anh trai Tèo đố em:

Cho ~n~ thẻ tre ~a_1, a_2, ..., a_n~ với thẻ thứ ~i~ có độ dài ~a_i~ (đơn vị đo chiều dài). Tèo sẽ lấy các thẻ tre có độ dài tương ứng để tạo thành các hình chữ nhật (Không bẻ gãy hay chắp nối để thay đổi chiều dài thẻ tre và hình vuông cũng được xem là hình chữ nhật).

Tí muốn Tèo ghép được một hình chữ nhật càng to càng tốt mà độ dài của các cạnh được lấy từ các thẻ tre đã cho. Một hình chữ nhật sẽ được ghép từ ~4~ thẻ tre.

Yêu cầu: Hãy cho biết tổng độ dài ~2~ cạnh (chiều dài, chiều rộng) và chu vi của hình chữ nhật lớn nhất mà Tèo có thể ghép được.

Input

Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^6)~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^6; 1 ≤ i ≤ n)~.

Output

Dòng đầu là tổng độ dài ~2~ cạnh (chiều dài, chiều rộng) hình chữ nhật;

Dòng tiếp theo là chu vi lớn nhất của hình chữ nhật có thể ghép được.

Lưu ý: Nếu không thể ghép được thì ghi ~0~.

Sample Input 1

9
3 4 9 5 4 9 2 1 2

Sample Output 1

13
26

Sample Input 2

6
3 8 1 8 2 7

Sample Output 2

0

Subtask

• Subtask 1: Có ~30\%~ số test tương ứng với ~30\%~ số điểm với ~n \le 50~.

• Subtask 2: Có ~40\%~ số test tương ứng với ~40\%~ số điểm với ~50 < n\le 1000~.

• Subtask 3: Có ~30\%~ số test còn lại tương ứng với ~30\%~ số điểm không có ràng buộc gì thêm.

Giải thích

• Test 1:

Có ~3~ cách ghép thành hình chữ nhật có chiều dài và chiều rộng như sau: ~(4, 9); (4, 2); (9, 2)~.

Tổng độ dài ~2~ cạnh là ~4 + 9 = 13~.

Chu vi lớn nhất là ~(4 + 9) \times 2 = 26~.

• Test 2

Không thể ghép thành hình chữ nhật nào cả.