Giả Kim Thuật

Đ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

Bessie đang học giả kim thuật. Cô ấy bắt đầu với $a_{i}$ đơn vị kim loại $i$ ( $1 \leq i \leq N$ , $N \leq 100$ ). Cô ấy biết $K$ công thức ( $1 \leq K < N$ ), mỗi công thức cho phép kết hợp một đơn vị của mỗi kim loại thành phần để tạo ra một đơn vị kim loại có số hiệu lớn hơn tất cả các kim loại thành phần. Mỗi kim loại có tối đa một công thức để tạo ra nó.

Hãy tìm số đơn vị kim loại $N$ tối đa có thể đạt được sau bất kỳ số lần biến đổi nào.

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $0 \leq a_{i} \leq 10^{4}$ )
Dòng 3: Số nguyên $K$
$K$ dòng tiếp theo: Mỗi dòng chứa hai số $L$ và $M$ , tiếp theo là $M$ số nguyên — danh sách các kim loại thành phần để tạo ra kim loại $L$

Dữ liệu ra

Một số nguyên duy nhất — số đơn vị kim loại $N$ tối đa có thể tạo được.

Ràng buộc

$1 \leq N \leq 100$
$0 \leq a_{i} \leq 10^{4}$
$1 \leq K < N$
Mỗi kim loại có tối đa một công thức

Ví dụ

Input	Output	Giải thích
5 2 0 0 1 0 3 5 2 3 4 2 1 1 3 1 2	1	Biến kim loại 1 thành 2, rồi 2 thành 3, rồi kết hợp 3 và 4 để tạo 5.

Bình luận

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