Sinh nhật LQDOJ 2023 - Contest ôn tập THT bảng C2 - 2023 #02

_minhduc quyết định rủ shiba lặn lội xa xôi để đến tham dự lễ hội cosplay Nubustes. Ở lễ hội, shiba và _minhduc có gặp một số anh chị hóa trang thành một số nhân vật rất dễ thương. Chính vì thế, họ quyết định lôi điện thoại ra và lượn lờ quanh cả cái khu vực lễ hội để xin được chụp ảnh chung. Trong lễ hội có tất cả \(n\) nhân vật hóa trang, nhân vật thứ \(i\) có độ đẹp trai/ xinh gái là \(a_{i}\), nếu chụp ảnh với nhân vật này thì sẽ nhận được độ thỏa mãn một lượng bằng \(b_{i}\). shiba và _minhduc đã quyết định là sẽ chỉ chụp ảnh với người có độ đẹp trai/ xinh gái thấp hơn hoặc bằng mình, căn bản là vì họ không đủ tự tin để xin chụp ảnh với những nhân vật còn lại.

_minhduc và shiba chưa quyết định được cách ăn mặc do họ nhất quyết là phải mặc đồ đôi để đi chơi với nhau và giờ họ đang mặc thường phục, họ quyết định là sẽ đi thay đồ, mỗi bộ đồ đôi lại đem lại cho họ độ đẹp trai khác nhau. Có tất cả \(m\) cách phối đồ mà hai người họ nghĩ ra, cách phối đồ thứ \(j\) thì _minhduc sẽ có độ đẹp trai là \(x_{i}\) còn shiba sẽ có độ đẹp trai là \(y_{i}\).

Hỏi tổng độ thỏa mãn lớn nhất có thể nhận được của _minhduc và shiba là bao nhiêu?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(m\) (\(n,m \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a_{i}\) và \(b_{i}\), miêu tả nhân vật hóa trang thứ \(i\) trong lễ hội (\(a_{i} \le 10^{16}, b_{i} \le 10^{12}\)).
• Dòng thứ \(n+2\) chứa dãy \(x\) gồm \(m\) số nguyên dương (\(x_{i} \le 10^{16}\)).
• Dòng thứ \(n+3\) chứa dãy \(y\) gồm \(m\) số nguyên dương (\(y_{i} \le 10^{16}\)).

Output

• Với mỗi cách phối đồ, in ra trên một dòng là độ thỏa mãn lớn nhất có thể nhận được. Lưu ý nếu \(2\) người cùng chụp với một nhân vật thì tính độ thỏa mãn \(2\) lần, còn nếu chỉ \(1\) người chụp thì chỉ tính \(1\) lần.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n,m \le 10^3\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

3 2
1 3
2 4
3 7
1 2
3 2

17
14

Cho một dãy số gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\).

Yêu Cầu: Cho một số nguyên dương \(M\), bạn hãy đếm \(x\in[1;M]\) thỏa mãn rằng \(gcd(a_i,x) = 1\) với mọi \(1 \le i \le N\).

Biết rằng \(gcd(a,b)\) là ước chung lớn nhất của \(a\) và \(b\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((1 \le N,M \le 10^6)\).
• Dòng tiếp theo chứa dãy số nguyên dương \(a_1,a_2,...,a_N\) \((1 \le a_i \le 10^6)\).

Output

• Dòng đầu tiên in ra số lượng \(x\in[1;M]\) thỏa mãn yêu cầu đề bài.
• Các dòng tiếp theo in ra chúng theo thứ tự tăng dần, mỗi số cách nhau một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(N \times M \le 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): Có \(N,M \le 10^5\) và \(a_i \le 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 12
6 1 5

3
1
7
11

Sau một ngày đi chơi siêu cháy ở lễ hội cosplay Nubustes, shiba và _minhduc phải trở về nhà của mình để còn tiếp tục làm việc và viết đề, sinh test cho các LQDOJ-er :Đ

Giữa hai tỉnh có tất cả \(n\) địa điểm và có \(m\) con đường nối các điểm này với nhau. Hiện tại, lễ hội Nubustes đang diễn ra tại điểm \(1\), _minhduc và shiba cần phải về tới nhà tại điểm \(n\). Các con đường này đều là đường hai chiều, con đường thứ \(i\) nối hai địa điểm \(u_{i}\) và \(v_{i}\) với nhau. Có hai cách đi trong một con đường:

• Đi bằng xe máy của hai người và tốn chi phí bằng một lượng \(c_{i}\) đồng.
• Dắt xe máy lên một chiếc xe buýt và phải trả cho tài xế chi phí bằng một lượng \(d_{i}\) đồng.

Tuy nhiên, mỗi lần đổi giữa đi xe máy và đi xe buýt, hai người đều mất chi phí bằng \(1\). Ví của hai người có thể chứa tối đa \(k\) đồng. Ban đầu, tại lễ hội Nubustes họ đã có đầy ví tiền. Ngoài ra, ở mỗi điểm đều có ngân hàng, ngân hàng cho phép rút một số tiền bất kì, tuy nhiên cứ với mỗi \(100\) đồng bạn rút bạn phải trả chi phí là \(1\) đồng cho ngân hàng, ngoài ra nếu bạn rút một phần tiền chưa đạt đên \(100\) đồng bạn vẫn sẽ mất \(1\) đồng, ví dụ: bạn rút \(500\) đồng bạn phải trả cho ngân hàng phí là \(5\) đồng, bạn rút \(501\) đồng bạn phải trả cho ngân hàng phí là \(6\) đồng.

Hỏi chi phí ít nhất để hai người có thể về tới nhà là bao nhiêu?

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,m\) (\(n \le 10^4\), \(m \le 10^5\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên biểu diễn một con đường (\(1 \le u,v \le n, 0 \le c,d \le 10^3\)).
• Dòng cuối cùng chứa số nguyên dương \(k\) (\(k \le 10^3\)).
• Dữ liệu đảm bảo con đường nào cũng có thể đi được nếu ví tiền của hai người đầy.

Output

• Một dòng chứa một số nguyên duy nhất là chi phí để di chuyển từ lễ hội Nubustes về đến nhà của _minhduc và shiba.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(d_{i} = 1000\) với \(i = 1,2,3...,m\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

3 2
1 2 1 99
2 3 99 1
1000

3

Sau kì thi TST đầy căng thẳng và áp lực, cht_duong với lmqzzz với quyết định chơi cờ với nhau.
Sau \(7749\) trận, cht_duong và lmqzzz bắt đầu chơi cờ theo những cách có \(1-0-2\), kiểu như chơi cờ thiếu hậu, thiếu xe, đen trắng xếp loạn… Nhà lmqzzz có rất nhiều con vua nên anh ta lấy chúng ra nghịch, và họ vô tình phát minh một bài toán rất thú vị.
Cho bàn cờ kích thước \(N \times N\). Các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Đếm số cách xếp \(K\) vua lên bàn cờ sao cho không có con nào tấn công nhau.

Một cách xếp hợp lệ:

Một cách xếp không hợp lệ:

Biết rằng vua tấn công tất cả các ô chung đỉnh hoặc chung cạnh với ô nó đứng, và mỗi ô đặt không quá một quân cờ. Nói cách khác, vua đứng ở ô \((i,j)\) sẽ tấn công tất cả các ô \((x,y)\) thỏa mãn rằng:

• \(1 \le x,y \le N\);
• \(max(|x−i|,|y−j|) \le 1\).

Hai người họ muốn có một chương trình để giúp họ tính được kết quả mong muốn của bài toán. Mặc dù là một TST-er, nhưng cht_duong đang trầm kẽm và lmqzzz phải chuẩn bị đi ôn để tham gia APIO sắp tới nên không ai code được bài này. Là một TST-er tương lai, bạn hãy giúp bọn họ :Đ

Lưu ý: Có thể có nhiều hơn một con vua ở cùng một hàng hoặc một cột, miễn là chúng không tấn công nhau.

Input

• Gồm hai số nguyên dương \(N\) và \(K\) \((1 \le N \le 12,1 \le k \le N^2)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(1 \le N \le 4\).
• Subtask \(2\) (\(40\%\) số điểm): Có \(5 \le N \le 8\).
• Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2

16