Công ty VNG đang tiến hành thử nghiệm ~N~ sản phẩm trò chơi mới. Khi phát hành một sản phẩm, công ty sẽ được tài trợ một số tiền nhất định từ các nhà đầu tư. Nếu phát hành sản phẩm thứ ~i~ sẽ được tài trợ ~P_i~ đô la. Tuy nhiên, để phát hành một sản phẩm, công ty cần phải sử dụng một số tài nguyên như máy chủ, cơ sở dữ liệu, nhân lực, v.v. Để sử dụng một tài nguyên, công ty cần phải trả một khoản phí nhất định. Có tất cả ~M~ loại tài nguyên khác nhau, và chi phí khi sử dụng tài nguyên thứ ~j~ là ~C_j~ đô la.

Bạn là một nhà quản lý tài ba với khả năng lập trình siêu việt, công ty giao cho bạn một nhiệm vụ quan trọng, đó là xác định những sản phẩm nào nên phát hành và sử dụng những loại tài nguyên nào để tối đa hoá lợi nhuận. Lợi nhuận được tính bằng tổng số tiền được tài trợ trừ đi tổng số tiền phải trả cho việc sử dụng tài nguyên. Lưu ý, một sản phẩm chỉ có thể được phát hành khi có đủ bộ tài nguyên yêu cầu, và một loại tài nguyên có thể sử dụng chung cho các sản phẩm khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N, M \le 1000~)
• Dòng thứ hai chứa ~N~ số nguyên thể hiện số tiền được tài trợ cho các sản phẩm ~p_1, p_2, ..., p_N~ ~(1 \le p_i \le 10^6)~
• Dòng thứ ba chứa ~M~ số nguyên thể hiện chi phí khi sử dụng các tài nguyên ~c_1, c_2, ..., c_M~ ~(1 \le c_j \le 10^6)~
• ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số ~a_{i1}, a_{i2}, ..., a_{iM}~ với ~a_{ij} = 1~ nếu sản phẩm thứ ~i~ cần sử dụng tài nguyên thứ ~j~, ngược lại ~a_{ij} = 0~ nếu không cần sử dụng.

Output

• Dòng đầu tiên ghi tổng số tiền lợi nhuận tối đa có thể đạt được.
• Dòng thứ 2 liệt kê danh sách các sản phẩm được phát hành (nếu không có sản phẩm nào được phát hành, in ra 0)
• Dòng thứ 3 liệt kê danh sách các tài nguyên được sử dụng (nếu không có tài nguyên nào được sử dụng, in ra 0)

Subtasks

• Subtask 1 (25%): ~N, M \le 20~
• Subtask 2 (25%): ~N \le 20~ hoặc ~M \le 20~
• Subtask 3 (25%): ~N, M \le 100~
• Subtask 4 (25%): Không có ràng buộc gì thêm

Nếu chỉ tìm được tổng lợi nhuận tối đa, thì được ~50\%~ số điểm.

Sample

Input

3 4
4 10 11
6 2 3 7
1 0 0 1
0 1 1 0
0 1 0 0

Output

16
2 3
2 3

Giải thích

Các thí nghiệm được thực hiện là 2 và 3. Các dụng cụ cần sử dụng là 2 và 3.

Tháng 4.2024, Zalo AI ra mắt chatbot Kiki Giao thông phiên bản thử nghiệm. Nam là 1 tester và anh đang muốn kiểm tra thử độ hiệu quả của Kiki trong việc tìm ra các đường đi tối ưu.
Bỗng nhiên, Nam nghĩ ra 1 cách để làm khó chú Zalo AI này bằng cách đặt một câu hỏi về tối ưu trong việc xây cầu.

Bài toán Nam đưa ra như sau:

• Cho ~n~ cột đá, Kiki cần dựng đứng ~n~ cột đá này và xếp chúng thành 1 đường thẳng theo 1 thứ tự nhất định và đặt ~n-1~ tấm gỗ giữa các cặp cột đá liền kề để làm 1 cây cầu.
• Chiều cao của ~n~ cột đá lần lượt là ~a_1, a_2, ..., a_n~.
• Khoảng cách giữa 2 cột đá liền kề luôn là 1
• Chiều ngang (độ dày) của các cột đá là không đáng kể.
• Luôn có ít nhất 2 cột đá

Nam yêu cầu Kiki phải tìm thứ tự xếp sao cho đường đi từ cái cột đầu tiên tới cái cột cuối dùng là ngắn nhất, và trả về kết quả là tổng chiều dài của các tấm gỗ được sử dụng.

Kiki đã nhanh chóng đưa ra đáp án của mình, nhưng Nam lại không biết được rằng đáp án này có phải là chính xác hay không nên đã nhờ bạn tính toán và sau đó sẽ so sánh 2 kết quả với nhau. Hãy giúp Nam kiểm tra kết quả!

Input format

• Dòng đầu tiên là số nguyên n (~2 \leq n \leq 10^5~)
• Dòng thứ hai chứa n số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^4~)

Output format

• In ra duy nhất 1 số thực tổng chiều dài nhỏ nhất của các tấm gỗ
• Câu trả lời sẽ được chấp nhận nếu sai số ~\leq -10^6~

Constraints

Subtask 1 (gồm 30% số điểm): ~n \leq 15 ~, ~a_i \leq 100~
Subtask 2 (gồm 70% số điểm): ~n \leq 10^5~, ~a_i \leq 10^4~

Sample Input 1:

2
1 1  

Sample Output 1:

1.000000

Sample Input 2:

2  
3 4

Sample Output 2:

1.414214

Giải thích ví dụ

Sample test 1
Có 1 cách xếp duy nhất:

• (1 1): ~\sqrt{(1-1)^2 + 1}~ = 1

Tổng chiều dài cần dùng nhỏ nhất là 1.000000.

Sample test 2
Có tổng cộng 2 cách xếp:

• (3 4) : ~\sqrt{(3-4)^2 + 1}~ = 1.414214
• (4 3) : ~\sqrt{(4-3)^2 + 1}~ = 1.414214

Tổng chiều dài cần dùng nhỏ nhất là 1.414214.

Tuấn là một cậu bé ham học hỏi và thích lập trình. Cậu tìm được một bài toán nhưng vẫn không tìm được cách giải thích hợp. Hãy giúp cậu giải quyết bài toán này nhé.

Cho một dãy số gồm ~N~ số nguyên, ~A_1, A_2, \dots, A_N~. Có ~Q~ truy vấn, mỗi truy vấn gồm 2 số nguyên ~L, R~. Nhiệm vụ của cậu là tìm số lượng đoạn con liên tiếp nhiều nhất trong đoạn từ ~L~ đến ~R~ mà tổng các số trong mỗi đoạn con đó bằng ~0~. Các đoạn con này không được giao nhau.

Input

• Dòng thứ nhất gồm ~2~ số nguyên dương ~N, Q~ ~(1 \le N, Q \le 10^6)~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(-10^6 \le A_i \le 10^6)~.
• ~Q~ dòng tiếp theo gồm 2 số nguyên ~L, R~ ~(1 \le L \le R \le N)~.

Output

• Gồm ~Q~ dòng, dòng ~i~ gồm một số nguyên là số lượng đoạn con liên tiếp nhiều nhất trong đoạn ~[L_i, R_i]~ có tổng bằng ~0~.

Scoring

• Subtask 1 (Gồm 30% số điểm): ~N, Q \leq 10^3~
• Subtask 2 (Gồm 70% số điểm): ~N, Q \le 10^6~

Sample Input 1

5 4
-2 2 -2 8 -6 
2 5
1 5
1 4
1 2

Sample Output 1

1
2
1
1

Sample Input 2

4 2
0 0 0 0
1 2
1 4

Sample Output 2

2
4

Notes

Trong ví dụ đầu tiên, dãy gồm ~5~ phần tử và ~4~ truy vấn:

• Với truy vấn thứ nhất gồm đoạn ~[2, -2, 8, -6]~, đoạn con có tổng bằng ~0~ là ~[[2, -2], 8, -6]~ hoặc ~[2, [-2, 8, -6]]~
• Với truy vấn thứ hai gồm đoạn ~[-2, 2, -2, 8, -6]~, số lượng được có tổng bằng ~0~ lớn nhất là ~[[-2, 2], [-2, 8, -6]]~
• Với truy vấn thứ ba gồm đoạn ~[-2, 2, -2, 8]~, đoạn con có tổng bằng ~0~ là ~[[-2, 2], -2, 8]~ hoặc ~[-2, [2, -2], 8]~
• Với truy vấn cuối cùng gồm đọan ~[-2, 2]~, có duy nhất chính nó có tổng là ~0~

Chú ý giới hạn thời gian của bài toán

Cho một số nguyên ~N~, yêu cầu phân tích số ~N~ thành các thừa số nguyên tố.

Biết rằng số nguyên ~N~ được tạo thành từ đoạn code như sau:

function isPrime(N):
    // Hàm dùng để kiểm tra N có phải số nguyên tố không.


function MakeNumber(S, K):
    N = 1
    while K > 0:
        #                 vv lấy ngẫu nhiên giữa 1 và 100.
        if isPrime(S) and random_int(1, 100) == 1:
            K -= 1
            N *= S
        S += 1
    return N

Trong đó, hàm ~random\_int~ là hàm ngẫu nhiên phân phối đều.

Ngoài ra, bạn sẽ được biết thêm hai tham số ~S, K~ được truyền vào hàm ~MakeNumber~.

Input

• Dòng đầu tiên chứa hai số ~S, K~.
• Dòng thứ hai chứa số nguyên ~N~.

Constraints

• ~1 \leq S \leq 10^{18}~
• ~1 \leq S \leq N \lt 10^{2000}~
• ~2 \leq K \leq 100~

Output

• In ra các thừa số nguyên của số nguyên ~N~ theo thứ tự tăng dần. Biết rằng giá trị của các thừa số nguyên tố trong đáp án sẽ không vượt quá ~9,223,372,036,854,775,807~.

Subtask

• Subtask 1 ~(40\%)~: ~N \leq 2\times 10^{18}~, ~S, K~ được đảm bảo phù hợp với ~N~ được tạo ra.
• Subtask 2 ~(60\%)~: Không có giới hạn gì thêm.

Sample input

123 2
62291

Sample output

167 373

Mô tả đề bài

Ngân là một thành viên trong team tổ chức sự kiện tại VNG, sắp tới Ngân sẽ có rất nhiều sự kiện cần tham gia. Là một cô gái điệu đà, Ngân luôn thích trang điểm thật xinh khi tham gia các sự kiện này. Có ~n~ sự kiện và ~m~ cách lựa chọn thời gian trang điểm. Sự kiện thứ ~i~ sẽ có thời điểm bắt đầu là ~a_{i}~ và thời điểm kết thúc là ~b_{i}~ ~(1 \le i \le n)~. Cách trang điểm ~j~ sẽ có hiệu quả trong khoảng thời gian từ thời điểm ~c_{j}~ đến thời điểm ~d_{j}~ ~(1 \le j \le m)~. Nhiệm vụ của bạn là giúp Ngân tìm xem cách trang điểm nào giúp Ngân tham gia được nhiều sự kiện nhất trong ~m~ cách trên.

Lưu ý: Ngân chỉ có thể tham gia những sự kiện mà thời gian bắt đầu lẫn kết thúc đều nằm trong khoảng thời gian mà cách trang điểm Ngân chọn có thể duy trì hiệu quả. Ví dụ Ngân chọn cách trang điểm có hiệu quả từ thời điểm ~c_{j}~ đến ~d_{j}~ thì Ngân chỉ có thể tham gia những sự kiện có thời điểm tham gia và kết thúc là ~a_{i}~ và ~b_{i}~ sao cho ~c_{j} \le a_{i} \le b_{i} \le d_{j}~

Giới hạn: ~1 \le n, m \le 10^5~ , ~1 \le a_{i}, b_{i} \le 10^9~, ~1 \le c_{j}, d_{j} \le 10^9~.

Input

Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~.

~n~ dòng tiếp theo mỗi dòng chứa 2 số nguyên ~a_{i}~ và ~b_{i}~.

~m~ dòng tiếp theo mỗi dòng chứa 2 số nguyên ~c_{j}~ và ~d_{j}~.

Output

In ra số sự kiện nhiều nhất mà Ngân có thể tham gia bằng cách chọn 1 trong những cách trang điểm được cho.

Sample Input

4 1
1 3
1 2 
3 3
4 5
1 3 

Sample Output

3

Giải thích

Ở đây Ngân chỉ có một cách trang điểm duy nhất và cách trang điểm này có hiệu quả từ thời điểm ~1~ đến thời điểm ~3~ nên Ngân có thể dùng nó để tham gia sự kiện ~1, 2~ và ~3~.