Bài tập

Cho một tập hợp \(A\) gồm \(n\) số nguyên đôi một khác nhau. Một chỉnh hợp không lặp chập \(k\) là một dãy gồm \(k\) phần tử khác nhau lấy từ \(A\), trong đó thứ tự các phần tử có ý nghĩa (dãy \((1, 4)\) và \((4, 1)\) là hai chỉnh hợp khác nhau).

Hãy liệt kê toàn bộ các chỉnh hợp không lặp chập \(k\) của \(A\) và đếm xem có bao nhiêu chỉnh hợp.

Input

• Dòng đầu chứa hai số nguyên \(k\) và \(n\).
• Dòng thứ hai chứa \(n\) số nguyên phân biệt là các phần tử của \(A\), mỗi số có giá trị tuyệt đối không quá \(5 \cdot 10^9\).

Output

• In mỗi chỉnh hợp trên một dòng (các phần tử cách nhau một dấu cách). Các chỉnh hợp được in theo thứ tự từ điển tăng dần (so sánh theo giá trị số).
• Dòng cuối cùng in số lượng chỉnh hợp đã liệt kê.

Constraints

• \(1 \le k \le n \le 8\)
• Các phần tử của \(A\) đôi một khác nhau, \(|A_i| \le 5 \cdot 10^9\)

Sample Input

2 3
8 -2 5

Sample Output

-2 5
-2 8
5 -2
5 8
8 -2
8 5
6

Cho dãy \(n\) số nguyên \(A_1, A_2, \dots, A_n\) và một số nguyên \(M\). Giữ nguyên thứ tự các số, ta chèn vào mỗi trong \(n-1\) khoảng giữa hai số liên tiếp đúng một trong ba dấu phép toán +, -, *, tạo thành một biểu thức. Biểu thức được tính theo quy tắc toán học thông thường: phép nhân được thực hiện trước, sau đó mới đến cộng và trừ. Ví dụ với dãy \([3, 4, 5]\), biểu thức 3+4*5 có giá trị \(23\).

Hãy liệt kê tất cả các biểu thức có giá trị đúng bằng \(M\).

Các số được viết đúng như trong dữ liệu, số âm giữ nguyên dấu trừ (ví dụ 2+-3, 4*-1, 5--2). Biểu thức không chứa khoảng trắng.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(M\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_1, \dots, A_n\).

Output

In mỗi biểu thức thỏa mãn trên một dòng, theo thứ tự từ điển tăng dần của xâu ký tự (theo mã ASCII: * đứng trước +, + đứng trước -). Nếu không có biểu thức nào thì không in gì.

Với \(n = 1\), biểu thức chỉ gồm số \(A_1\) và được in ra nếu \(A_1 = M\).

Constraints

• \(1 \le n \le 16\)
• \(|M| \le 2 \cdot 10^{18}\)
• \(|A_i| \le 10^9\)
• Giá trị trung gian của biểu thức có thể rất lớn; kết quả so sánh với \(M\) là giá trị toán học chính xác.
• Để dữ liệu ra không quá lớn, số biểu thức thỏa mãn không quá \(5 \cdot 10^5\).

Sample Input

5 18
2 3 4 -1 5

Sample Output

2*3*4+-1-5
2+3*4+-1+5

Explanation

\(2 \cdot 3 \cdot 4 + (-1) - 5 = 24 - 1 - 5 = 18\) và \(2 + 3 \cdot 4 + (-1) + 5 = 2 + 12 - 1 + 5 = 18\). Không còn cách nào khác cho giá trị \(18\).

Cho dãy \(n\) số nguyên \(A_1, A_2, \dots, A_n\) và một số nguyên \(M\). Giữ nguyên thứ tự các số, ta chèn vào mỗi trong \(n-1\) khoảng giữa hai số liên tiếp một trong hai dấu + hoặc -, được một biểu thức. Ví dụ với dãy \([3, 4, 5]\) ta có thể tạo ra \(3+4-5\), giá trị bằng \(2\).

Hãy liệt kê tất cả các biểu thức có giá trị đúng bằng \(M\).

Cách in biểu thức. Số đầu tiên được in nguyên dạng \(A_1\) (kèm dấu - nếu âm). Với \(i \ge 2\), ta in dấu hiệu dụng rồi đến giá trị tuyệt đối \(|A_i|\), trong đó dấu hiệu dụng là dấu mà \(|A_i|\) thực sự đóng góp vào tổng: nếu chèn + trước \(A_i\) thì dấu hiệu dụng là dấu của \(A_i\), nếu chèn - thì là dấu ngược lại (khi \(A_i = 0\) thì lấy đúng dấu được chèn). Chẳng hạn với dãy \([2, -3, 0]\), việc chèn - trước \(-3\) được in là +3, và hai cách chèn dấu trước số \(0\) cho hai biểu thức khác nhau 2+3+0 và 2+3-0. Nhờ vậy các biểu thức không có khoảng trắng và mỗi cách chèn dấu cho ra đúng một dòng.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(M\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_1, \dots, A_n\).

Output

In mỗi biểu thức thỏa mãn trên một dòng, theo thứ tự từ điển tăng dần của xâu ký tự (theo mã ASCII, tức + đứng trước -). Nếu không có biểu thức nào thì không in gì.

Constraints

• \(1 \le n \le 21\), \(|M| \le 2 \cdot 10^9\)
• \(|A_i| \le 10^9\)

Sample Input 1

4 4
6 3 -2 1

Sample Output 1

6-3+2-1

Sample Input 2

4 6
3 -2 0 5

Sample Output 2

3-2+0+5
3-2-0+5

Explanation

Ở ví dụ 2, chèn + trước \(-2\) (đóng góp \(-2\)), rồi +0 hoặc -0 (đóng góp \(0\)), rồi + trước \(5\): giá trị \(3-2+0+5 = 6\). Hai cách chèn dấu khác nhau ở số \(0\) nên có hai dòng.

Bạn Nam là một tay vợt cầu lông chuyên nghiệp. Trong năm có \(n\) giải đấu, giải thứ \(i\) diễn ra vào ngày \(a_i\) và mang lại tiền thưởng \(b_i\) cho người tham gia. Để giữ sức khoẻ, huấn luyện viên yêu cầu hai giải mà Nam đăng ký phải cách nhau ít nhất \(k\) ngày, tức là với hai giải \(i \ne j\) được chọn thì \(|a_i - a_j| \ge k\).

Hãy chọn một tập giải đấu thoả yêu cầu sao cho tổng tiền thưởng là lớn nhất và in ra tổng đó.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1 \le a_2 \le \dots \le a_n\) là ngày diễn ra các giải.
• Dòng thứ ba chứa \(n\) số nguyên \(b_1, b_2, \dots, b_n\) là tiền thưởng của các giải.

Output

In ra một số nguyên là tổng tiền thưởng lớn nhất có thể nhận được.

Constraints

• \(1 \le n \le 10^5\), \(1 \le k \le 10^9\)
• \(1 \le a_i \le 10^9\) (không giảm dần)
• \(1 \le b_i \le 10^9\)

Sample Input 1

6 3
2 4 5 8 9 12
7 6 6 5 10 1

Sample Output 1

24

Sample Input 2

4 30
5 10 20 40
8 3 9 1

Sample Output 2

9

Explanation

Ở ví dụ 1 chọn các ngày \(2, 5, 9, 12\) (cách nhau ít nhất 3 ngày): \(7+6+10+1=24\). Ở ví dụ 2, \(k=30\) nên chỉ chọn được ngày 5 và 40 (tổng 9) hoặc riêng ngày 20 (tổng 9).