Hoàng yêu thích các số may mắn. Ta biết rằng một số là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ, các số 47, 744, 4 là số may mắn và 5, 17, 467 không phải. Hoàng muốn tìm số may mắn bé nhất có tổng các chữ số bằng n. Hãy giúp anh ấy.

Đầu vào: Dòng duy nhất chứa số nguyên dương n

Ràng buộc: 1<=n<=10^6;

Đầu ra: In ra đáp án của bài toán, nếu không tồn tại đáp án thì in ra -1

Input:

16

Output:

4444

Một dãy gồm n số nguyên không âm a1, a2,...., an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (n-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trằng đó để nhận được một biểu thức có giá trị lớn nhất. Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1 +69 là biểu thức có giá trị lớn nhất. Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2..., an và số nguyên dương k, hãy tìm cách đặt k dấu cộng và (n-1-k) dấu trừ vào (n-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Đầu vào: Dòng đầu chứa hai số nguyên dương n, k; Dòng thứ hai chứa n số nguyên không âm a1, a2,..., an;

Ràng buộc: 1 <= k < n ≤ 10^5; 0 <= a[i] ≤ 10^6

In ra giá trị lớn nhất của biểu thức

Input:

5 3
10 1 3 9 8

Output:

29

Trong lớp học có n bạn nam và m bạn nữ. Các bạn nam có chiều cao là a1, a2, ..., an. Các bạn nữ có chiều cao là b1, b2, .., bm. Nhân dịp lễ tổng kết cuối năm, cả lớp dự định tổ chức buổi khiêu vũ nhưng có điều kiện là trong một đôi khiêu vũ bất kỳ, bạn nam phải cao hơn bạn nữ. Và mỗi bạn không tham gia quá 1 đôi khiêu vũ. Hãy tính số lượng cặp đôi nhiều nhất thỏả mãn yêu cầu trên.

Đầu vào: gồm 3 dòng

• Dòng thứ nhất là hai số n, m mỗi số cách nhau một khoảng trắng.

• Dòng thứ hai gồm n số nguyên a1, a2, .., an là chiều cao các bạn nam.

• Dòng thứ ba gồm m số nguyên b1, b2, .... bm là chiều cao các bạn nữ.

Ràng buộc: 1 <= n,m <= 10^5; 1 <= a[i],b[i] <=10^6

Input:

5 5
2668 2956 20933 21199 24224
11521 13084 19573 25628 28958

Output:

3