KỲ THI THỬ CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM HỌC 2022-2023 (DAY 2 - PT#1)

Tuấn có một bộ bài gồm \(n\) quân bài được trải ra thành một dãy từ trái sang phải, trên mỗi quân bài ghi một số nguyên là giá trị của quân bài đó. Gọi giá trị của \(n\) quân bài lần lượt theo dãy trải ra là \(A_1, A_2, ..., A_n\). Tuấn đưa ra các định nghĩa như sau:

• Một đoạn con là một chuỗi các quân bài liên tiếp nhau trong dãy \(n\) quân bài ban đầu;
• Trọng số của một đoạn con là tổng các giá trị của các quân bài trong đoạn;
• Độ cân bằng của bộ bài là trọng số của đoạn con có trọng số lớn nhất trong dãy \(n\) quân bài.

Tuấn rủ Tú đến nhà chơi bài và yêu cầu Tú tính độ cân bằng của bộ bài theo định nghĩa trên. Sau khi Tú tính xong Tuấn tiếp tục đố Tú chỉnh sửa một số giá trị quân bài để bộ bài đạt độ cân bằng cao nhất với các nguyên tắc chỉnh sửa như sau:

• Đầu tiên, Tuấn đưa cho Tú một dãy \(n\) số nguyên \(B_1, B_2, \dots, B_n\);
• Có tối đa \(k\) lượt chỉnh sửa, mỗi lượt Tú được phép chọn một đoạn con các phần tử từ vị trí thứ \(l\) đến vị trí thứ \(r\) (\(1 \le l \le r \le n\)) và thực hiện phép gán \(A_i = A_i \cdot B_i\) với \(\forall i \in [l, r]\).

Yêu cầu: Hãy giúp Tú đưa ra được độ cân bằng lớn nhất với tối đa \(k\) lượt chỉnh sửa.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le n \le 10^5\); \(0 \le k \le 10\)).
• Dòng thứ hai chứa \(n\) số nguyên \(A_1, A_2, ..., A_n\) (\(|A_i| \le 1000\)).
• Dòng thứ ba chứa \(n\) số nguyên \(B_1, B_2, ..., B_n\) (\(|B_i| \le 10\)).

Output

• Ghi ra một số nguyên duy nhất là độ cân bằng lớn nhất tìm được của bộ bài sau khi sử dụng tối đa \(k\) lượt chỉnh sửa.

Example

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

13

3 0
-4 -10 -8
2 2 -1

-4

Scoring

• Có \(15\%\) số test ứng với \(k = 0\).
• Có \(15\%\) số test khác ứng với \(k = 1\) và \(n \le 5000\).
• Có \(20\%\) số test khác ứng với \(k = 1\).
• Có \(25\%\) số test khác ứng với \(k = 2\).
• \(25\%\) số test còn lại không có ràng buộc gì thêm.

Hoành Sơn là một địa điểm du lịch nổi tiếng trên toàn thế giới bởi sự hùng vĩ cũng như sự đa dạng phong phú về các dãy núi và những cây cầu bắc qua. Địa điểm du lịch Hoành Sơn có các dịch vụ tham quan theo yêu cầu. Cụ thể là bạn chỉ việc đưa ra yêu cầu của lộ trình, sau đó dịch vụ sẽ tính toán và đưa bạn đi qua các cây cầu và ngọn núi theo đúng yêu cầu về lộ trình.

Địa điểm du lịch ở đây có \(N\) ngọn núi và \(M\) cây cầu, mỗi cây cầu nối hai ngọn núi nào đó với nhau. Giữa hai ngọn núi bất kì có thể có nhiều cây cầu nối hai ngọn núi đó với nhau. Cũng có thể có những ngọn núi có những cây cầu tự nối với chính nó tạo ra hình vòng cung để những khách du lịch có thể đứng xung quanh ngọn núi tham quan và chụp ảnh. Hiểu đơn giản thì mô hình của khu du lịch là một đa đồ thị vô hướng \(N\) đỉnh \(M\) cạnh.

Các ngọn núi được đánh số từ \(1\) đến \(N\) và ngọn núi thứ \(i\) có độ cao là \(A_i\). Về độ dốc của các cây cầu thì nó được tính theo chênh lệch chiều cao của hai ngọn núi ở hai đầu cây cầu. Nói cách khác, nếu cây cầu nối hai ngọn núi \(x\) và \(y\) thì độ dốc của nó là \(|A_x - A_y|\).

Sau khi đạt giải quốc gia, Tuấn muốn tự thưởng cho mình chuyến du lịch đến Hoành Sơn sau cả năm trời ôn luyện vất vả và chuẩn bị bước vào đại học. Đến Hoành Sơn, Tuấn muốn thiết kế một hành trình “lên đỉnh siêu dốc", xuất phát từ một ngọn núi nào đó, đi đến các ngọn núi khác với điều kiện ngọn núi sau cao hơn ngọn núi trước, không những thế, độ dốc của cây cầu sau cũng phải lớn hơn độ dốc của cây cầu trước đó. Nghĩa là, nếu như Tuấn quyết định chọn một hành trình đi qua các ngọn núi theo thứ tự \(P_1, P_2, ..., P_k\) thì hành trình đó sẽ phải thỏa mãn tính chất:

Yêu cầu: Hãy giúp hướng dẫn viên du lịch tìm cho Tuấn hành trình “lên đỉnh siêu dốc” qua nhiều đỉnh núi nhất và trả lời thắc mắc của Tuấn là có bao nhiêu hành trình khác nhau đạt được nhiều đỉnh núi nhất như vậy. Hai hành trình gọi là khác nhau nếu như tồn tại một cây cầu của hành trình này không có trong hành trình kia hoặc ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) (\(1 \leq N \leq 3 \cdot 10^5, 1 \leq M \leq 5 \cdot 10^5\)).
• Dòng thứ hai chứa độ cao của \(N\) ngọn núi là \(N\) số nguyên dương \(A_1, A_2, ..., A_n\) (\(1 \leq A_i \leq 10^9\)).
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa cặp số nguyên dương \((U_i, V_i)\) là chỉ số hai ngọn núi là hai đầu của cây cầu thứ \(i\) (\(1 \leq U_i, V_i \leq N\)).

Output

• Dòng đầu tiên ghi ra một số nguyên là số lượng đỉnh núi của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng lộ trình khác nhau tìm được cho \(10^9 + 7\).

Example

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

3
1

Scoring

• Có \(20\%\) số test ứng với \(N \leq 20\).
• Có \(20\%\) số test khác ứng với \(N \leq 500\).
• Có \(20\%\) số test khác ứng với các ngọn núi xếp thành một dãy núi thẳng hàng với nhau, nói cách khác đồ thị tương ứng là một mạch thẳng.
• Có \(20\%\) số test khác ứng với \(M = N - 1\), và các đỉnh trong đồ thị liên thông với nhau.
• \(20\%\) còn lại không có giới hạn gì thêm.

Để mở đầu cho kỉ nguyên chinh phục vũ trụ, các nhà khoa học ở hành tinh Alpha đang tiến hành thiết kế một chiếc tàu vũ trụ. Trong đó, bộ phận quan trọng nhất là hệ thống động cơ của tàu.

Các nhà khoa học đã mô hình hóa vũ trụ thành hệ trục tọa độ \(Oxy\) trong không gian hai chiều, lấy hành tinh Alpha làm gốc tọa độ. Có \(n\) vị trí có thể lắp ráp động cơ trên tàu vũ trụ. Việc lắp ráp động cơ ở vị trí thứ \(i\) tốn chi phí là \(w_i\), và sẽ cho phép tàu di chuyển theo hướng \((a_i, b_i)\). Cụ thể, giả sử tàu đang nằm ở tọa độ \((x, y)\) thì khi sử dụng động cơ thứ \(i\) trong khoảng thời gian \(t\) (\(t\) là số thực không âm, có thể lớn tùy ý) tàu sẽ đi đến vị trí \((x + a_i \times t, y + b_i \times t)\).

Một trong những tiêu chí quan trọng nhất trong thiết kế hệ thống tên lửa là tàu phải đi đến được mọi địa điểm trong vũ trụ, tức là với mọi điểm \((x, y)\), tàu luôn có thể xuất phát từ gốc tọa độ và đi đến điểm \((x, y)\) chỉ bằng các động cơ được lắp ráp. Nói cách khác, giả sử tàu được lắp ráp động cơ ở các vị trí \(r_1, r_2, \ldots, r_k\) thì cần đảm bảo rằng, với mọi điểm \((x, y)\) luôn tồn tại một bộ số thực \(t_1, t_2, \ldots, t_k\) không âm sao cho \(a_{r_1} \times t_1 + a_{r_2} \times t_2 + \ldots + a_{r_k} \times t_k = x\) và \(b_{r_1} \times t_1 + b_{r_2} \times t_2 + \ldots + b_{r_k} \times t_k = y\).

Yêu cầu: Hãy giúp các nhà khoa học hành tinh Alpha chọn ra các vị trí cần lắp ráp động cơ sao cho tàu có thể đi đến được mọi điểm trong vũ trụ, và tổng chi phí lắp ráp động cơ là nhỏ nhất.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \times 10^5\)) cho biết số vị trí có thể lắp động cơ.
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa ba số nguyên \(a_i, b_i, w_i\) (\(|a_i|, |b_i| \le 10^9\), \(1 \le w_i \le 10^9\)) cho biết hướng và chi phí lắp ráp động cơ ở vị trí thứ \(i\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để lắp ráp động cơ sao cho tàu có thể đi đến mọi điểm. Trong trường hợp không tồn tại các lắp ráp động cơ thỏa yêu cầu đề bài, hãy ghi ra -1.

Example

7
0 3 2
0 3 3
1 -1 3
-2 4 2
-4 0 1
2 1 2
0 0 1

6

2
1 0 10
0 1 10

-1

Hạn chế

• Có \(30\%\) số test ứng với \(n \le 16\).
• Có \(20\%\) số test khác ứng với \(n \le 50\).
• Có \(30\%\) số test khác ứng với \(n \le 2000\).
• \(20\%\) số test còn lại không có ràng buộc gì thêm.