C. GRAPH

Cho một đồ thị có hướng có đỉnh và cạnh. Các đỉnh được đánh số từ đến . Đỉnh thứ của đồ thị có hai giá trị và . Ta có quy trình tính như sau:

• Bước Đánh dấu đỉnh ;
• Bước Tìm một đỉnh chưa được đánh dấu sao cho tổng các giá trị (với mọi đã được đánh dấu và có cạnh nối từ đến ) đạt ít nhất . Sau đó đánh dấu và tiếp tục thực hiện bước cho đến khi không tìm được thỏa mãn;
• là số đỉnh được đánh dấu sau khi kết thúc.

Hãy tìm giá trị nhỏ nhất của và đếm số lượng đỉnh mà đạt giá trị nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên bao gồm hai số nguyên dương và là số đỉnh và số cạnh của đồ thị;
• Dòng thứ hai bao gồm số ;
• Dòng thứ a bao gồm số ;
• M dòng tiếp theo mỗi dòng gồm hai số miêu tả một cạnh của đồ thị nối từ đến .

Dữ liệu ra:

• Gồm hai số nguyên viết trên cùng một dòng ngăn cách bởi một dấu cách, số thứ nhất là giá trị nhỏ nhất của và số thứ hai là số lượng đỉnh mà đạt giá trị nhỏ nhất.

Ví dụ

Dữ liệu vào:

6 8
1 1 1 1 1 1
1 1 1 1 1 2
1 2
2 3
3 4
4 5
3 6
5 6
6 2
5 2

Dữ liệu ra:

5 5

Giải thích:

• Trừ đỉnh có ra thì còn lại đều ra

Giới hạn:

• Yêu cầu in ra cả hai số. Nếu bạn chỉ in ra được đúng giá trị đầu tiên, bạn nhận được số điểm của test đó.
• Trong tất cả các test ;
• Subtask số điểm có và ;
• Subtask số điểm còn lại có và .