Bài tập

Hai bạn được phát \(N\) lá bài, lá thứ \(i\) ghi một số nguyên dương \(A_i\). Hai bạn phải chơi đúng \(P\) lượt. Ở mỗi lượt, hai bạn chọn một lá bài, chọn một chữ số của số ghi trên lá đó và đổi nó thành một chữ số khác tuỳ ý sao cho số mới vẫn hợp lệ (không được có chữ số \(0\) ở đầu), rồi ghi số mới vào lá bài đó. Cùng một lá bài có thể được chọn nhiều lần ở các lượt khác nhau.

Ví dụ với số \(25321\) có thể đổi thành \(20321\), \(95321\), \(25320\) hay \(25921\), nhưng không thể đổi thành \(05321\).

Sau \(P\) lượt, hãy tìm tổng lớn nhất của \(N\) số trên các lá bài.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(P\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

In ra một số nguyên là tổng lớn nhất có thể.

Constraints

• \(1 \le N \le 5 \cdot 10^6\).
• \(1 \le P \le 2 \cdot 10^9\).
• \(1 \le A_i < 10^9\).

Sample Input 1

4 1
19 27 9 88

Sample Output 1

223

Sample Input 2

3 5
99 9 999

Sample Output 2

1107

Explanation

Ở ví dụ 1, tổng ban đầu là \(143\); đổi chữ số hàng chục của \(19\) thành \(9\) được \(99\) (tăng \(80\)), tổng là \(223\). Ở ví dụ 2 mọi chữ số đã là \(9\), tổng ban đầu \(1107\) là lớn nhất và có thể giữ nguyên sau \(5\) lượt (ví dụ đổi một chữ số \(9\) thành \(8\), rồi \(7\), rồi trở lại \(9\); sau đó đổi thêm \(9 \to 8 \to 9\) ở một chữ số khác).

Cho năm số nguyên \(a, b, c, d, x\). Hãy tính giá trị của đa thức \(P = a x^3 + b x^2 + c x + d\).

Input

Một dòng gồm năm số nguyên \(a, b, c, d, x\) cách nhau bởi dấu cách.

Output

In ra giá trị của \(P\).

Constraints

• \(1 \le a, b, c, d, x \le 10^4\)

Sample Input

2 3 4 5 10

Sample Output

2345

Trong một trò chơi ở hoàng cung, người ta tung nhiều đồng xu và ghi lại kết quả thành một xâu: mặt sấp ghi S, mặt ngửa ghi N.

Với mỗi xâu \(P\), nhà vua muốn biết tỉ lệ giữa số mặt sấp và số mặt ngửa dưới dạng phân số tối giản a/b, trong đó \(a\) là số lần S, \(b\) là số lần N sau khi đã chia cho ước chung lớn nhất. Ví dụ SSNSN có \(3\) lần S và \(2\) lần N nên tỉ lệ là 3/2.

Input

• Dòng đầu chứa số nguyên \(t\) là số xâu.
• \(t\) dòng tiếp theo, mỗi dòng là một xâu \(P\) chỉ gồm các ký tự S và N, chứa đủ cả hai loại ký tự.

Output

In ra \(t\) dòng, mỗi dòng là tỉ lệ ở dạng a/b tương ứng.

Constraints

• \(1 \le t \le 10\).
• \(2 \le |P| \le 10^5\).

Sample Input

3
NNNSN
SSNN
SNSNSSSS

Sample Output

1/4
1/1
3/1

Trên mặt phẳng tọa độ có \(M\) địa điểm có thể đặt cửa hàng pizza và \(N\) khu dân cư. Sắn sẽ chọn đúng \(K\) trong \(M\) địa điểm để mở cửa hàng. Mỗi cửa hàng phục vụ mọi khu dân cư nằm trong hình tròn tâm tại cửa hàng, bán kính \(R\) (khoảng cách từ khu dân cư đến cửa hàng nhỏ hơn hoặc bằng \(R\), khu nằm trên đường tròn cũng được phục vụ).

Khu dân cư thứ \(j\) có tọa độ \((x_j, y_j)\) và \(s_j\) người. Một khu được phục vụ nếu nó nằm trong vùng phục vụ của ít nhất một cửa hàng đã mở, và khi đó cả \(s_j\) người đều được tính (một khu nằm trong nhiều vùng phục vụ vẫn chỉ tính một lần).

Hãy chọn \(K\) địa điểm để tổng số người được phục vụ là lớn nhất, và in ra giá trị lớn nhất đó.

Input

• Dòng đầu gồm hai số nguyên \(K\) và \(R\).
• Dòng thứ hai gồm số nguyên \(M\) là số địa điểm có thể mở cửa hàng.
• \(M\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(X_i, Y_i\) là tọa độ của địa điểm thứ \(i\).
• Dòng tiếp theo gồm số nguyên \(N\) là số khu dân cư.
• \(N\) dòng cuối, mỗi dòng gồm ba số nguyên \(x_j, y_j, s_j\): tọa độ và số dân của khu dân cư thứ \(j\).

Output

In ra một số nguyên là số người tối đa có thể được phục vụ.

Constraints

• \(1 \le K \le 10\), \(1 \le R \le 500\)
• \(K \le M \le 20\)
• \(1 \le N \le 100\)
• Mọi tọa độ nằm trong đoạn \([-1000, 1000]\)
• \(1 \le s_j \le 100\)

Sample Input 1

2 3
4
0 0
6 0
3 4
9 4
5
1 1 4
3 0 6
5 1 2
7 3 5
4 4 3

Sample Output 1

15

Sample Input 2

1 2
3
0 0
5 5
9 9
3
1 1 5
5 6 7
9 8 2

Sample Output 2

7

Explanation

Ở ví dụ 1, mở cửa hàng tại \((0,0)\) phục vụ hai khu đầu (\(4+6=10\) người) và cửa hàng tại \((9,4)\) phục vụ khu \((7,3)\) (\(5\) người), tổng \(15\) là lớn nhất. Ở ví dụ 2 chỉ được mở một cửa hàng; chọn \((5,5)\) phục vụ khu \((5,6)\) với \(7\) người.