Thu Thập Tiền Xu

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có một đồ thị có hướng gồm $n$ phòng và $m$ đường hầm. Mỗi phòng $i$ chứa $k_{i}$ đồng tiền. Bạn có thể bắt đầu ở bất kỳ phòng nào, di chuyển qua các đường hầm, và dừng lại ở bất kỳ phòng nào. Hãy tìm số đồng tiền tối đa có thể thu thập được.

Lưu ý: Bạn thu thập tiền ở mỗi phòng khi đi qua. Nếu đi vào một phòng nhiều lần, chỉ thu tiền lần đầu.

Dữ liệu vào

Dòng 1: hai số nguyên $n$ và $m$ .
Dòng 2: $n$ số nguyên $k_{1}, k_{2}, \dots, k_{n}$ — số tiền trong mỗi phòng.
$m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ — đường hầm từ phòng $a$ đến phòng $b$ .

Dữ liệu ra

In một số nguyên duy nhất — số đồng tiền tối đa.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
$1 \leq k_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 4 4 5 2 7 1 2 2 1 1 3 2 4	16	Phòng 1 và 2 tạo thành chu trình: thu cả 4+5=9 tiền. Từ đó đi đến phòng 4 (+7). Tổng = 4+5+7=16.

Bình luận

Không có bình luận tại thời điểm này.