# Đề tham khảo #

## Bài 1: Tuyến xe buýt (BUS.*) ##

*Time limit: 1s*
*Memory limit: 1024 MB*

Minh là một chủ công ty chuyên cung cấp dịch vụ xe buýt công cộng và đang có ý định mở một vài tuyến xe buýt trên địa bàn Thành phố Hồ Chí Minh. Có tổng cộng $n$ trạm xe buýt khác nhau trong thành phố và $m$ tuyến đường một chiếu nối các trạm với nhau. Tuyến đường thứ $i$ nối có chiều từ trạm $u_i$ đến trạm $v_i$ và sẽ kiếm lại cho Minh $w_i$ đồng mỗi ngày và có thể có giá trị âm (khiến cho Minh bị lỗ $|w_i|$ đồng).

Một tuyến xe buýt hợp lệ là một tập các tuyến đường sao cho tạo được thành một chu trình: $u_1 - u_2 - u_3 - ... - u_k - u_{k+1} = u_1$ với điều kiện không có phần tử trong mảng $u$ nào xuất hiện quá 1 lần trừ $u_1$. Lợi nhuận của tuyến xe trong một ngày bằng tổng trọng số $w_i$ của các tuyến đường mà xe đi qua.

Trong $n$ trạm xe buýt nêu trên, có những trạm xe buýt thiết yếu và cấp lãnh đạo đề nghị Minh rằng các trạm xe thiết yếu phải nằm trên tuyến đường xe buýt và anh ấy đã chọn.

Minh có thể chọn nhiều tuyến xe buýt khác nhau với điều kiện không có hai tuyến xe buýt nào sử dụng chung một trạm với nhau và các trạm thiết yếu đều nằm trên một tuyến xe buýt nào đó.

**Yêu cầu:** Hãy giúp Minh tìm ra tổng tiền thu được trong một ngày nhiều nhất có thể hoặc chỉ ra rằng không có phương án chọn xe buýt nào hợp lệ.

**Dữ liệu:** Vào từ file văn bản **BUS.INP**
* Dòng đầu chứa 2 số nguyên $n, m$ $(1 \le n \le 100; 1 \le m \le 1000)$.
* Dòng thứ 2 dòng tiếp theo chứa số $n$ nguyên $a_1, a_2, ..., a_n$ $(a_i = 0 / 1)$ --- $a_i$ cho biết trạm thứ $i$ có phải là trạm thiết yếu hay không.
* Dòng thứ $i$ trong $m$ dòng tiếp theo chứa 3 số nguyên $u_i, v_i, w_i$ $(1 \le u_i, vi \le n; 1 \le |w_i| \le 10^9)$ --- cho biết tuyến đường thứ $i$ nối trạm xe $u_i$ với trạm $v_i$ với lợi nhuận $w_i$.

**Kết quả:** Ghi ra tập tin văn bản **BUS.OUT**
* Gồm một dòng duy nhất ghi số tiền Minh có thể kiếm được nhiều nhất hoặc ghi $-1$ nếu không có phương án hợp lệ.

**Ví dụ:**

**BUS.INP**

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

**BUS.OUT**

5


**Giải thích:** Minh chọn 2 tuyến xe buýt như sau:
- Tuyến đầu gồm các cạnh $(1, 2, 2), (2, 3, 2), (1, 3, -1)$ và có tổng số tiền là $2 + 2 - 1 = 3$.
- Tuyến thứ 2 gồm các cạnh $(4, 6, 5), (6, 7, -1), (7, 5, -1), (5, 4, -1)$ và có tổng số tiền là $5 + 1 - 1 - 1 = 2$.
- Các trạm 2, 4, 7 đều có tuyến xe buýt đi qua.
- Tổng số tiền Minh nhận được là 2 + 3 = 5.

**Ràng buộc:**
* 20% số test có $m \le 20$.
* 10% số test có điều kiện mỗi đỉnh chỉ thuộc không quá một chu trình.
* 10% số test có $a_i = 0$.
* 10% số test có $w_i = 0$.
* 50% số test không có ràng buộc nào thêm.

## Bài 2: Bảng vuông (SQUARE.*) ##

*Time limit: 1s*
*Memory limit: 1024 MB*
*Nguồn: https://codeforces.com/problemset/problem/526/F*

Bờm là một nhà phát triển game và đang được giao nhiệm vụ thiết kế và phát triển một trò chơi trên lưới vuông kích thước $n×n$ chứa đúng $n$ quân xe. Các quân xe được đặt sao cho không có 2 quân xe nào nằm chung hàng hoặc cột với nhau.

Bờm đang muốn thực hiện việc kiểm tra các chức năng của trò chơi. Tuy nhiên, vì kích thước bảng ô vuông có thể rất lớn nên Bờm muốn lựa chọn ra một phần hình vuông $k × k$ nhỏ hơn chứa chính xác $k$ quân xe để lấy làm dữ liệu mẫu kiểm tra.

Bờm tự hỏi có bao nhiêu cách để chọn trong lưới ô vuông ban đầu ban đầu một mảnh hình vuông $k × k$ $(1  \le  k \le n)$ như vậy. Hãy giúp Bờm tính con số này.

**Yêu cầu:** Hãy tìm bao nhiêu cách để chọn ra một mảnh hình vuông $k × k$ $(1  \le  k \le n)$ chứa đúng $k$ quân xe trên bảng ô vuông ban đầu.

**Dữ liệu:** Vào từ file văn bản **SQUARE.INP**
* Dòng đầu chứa số nguyên $n$ $(1 \le n \le 3 * 10 ^ 5)$ --- kích thước của bảng ô vuông.
* Dòng thứ $i$ trong $n$ dòng tiếp theo chứa 2 số nguyên $x_i, y_i$ $(1 \le x_i, y_i \le n)$ --- tọa độ hàng và cột của quân xe thứ $i$.

*Dữ liệu đảm bảo $x_i$ phân biệt, $y_i$ phân biệt.*

**Kết quả:** Ghi ra tập tin văn bản **SQUARE.OUT**
* Gồm một dòng duy nhất ghi số cách Bờm có thể chọn.

**Ví dụ:**

**SQUARE.INP**

5
1 1
4 3
3 2
2 4
5 5

**SQUARE.OUT**

10

**Ràng buộc:**
* 10% số test có $n \le 100$.
* 20% số test có $n \le 5000$.
* 70% số test có $n \le 3*10^5$.