CTAIN - Containers

Giới hạn
  • Thời gian: 5.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho n bình chứa nước (1 <= n <= 4). Ban đầu, mỗi bình đều chứa đầy nước. Bình i có dung lượng là oi, với 1 <= oi <= 49.

Bạn có thể thực hiện 1 trong 3 thao tác sau:

  1. Đổ tất cả nước ở trong bình A sang bình B. Thao tác này chỉ được thực hiện nếu bình B có đủ chỗ trống.
  2. Lấy 1 lượng nước ở bình A và đổ đầy hoàn toàn bình B.
  3. Đổ tất cả nước mà 1 bình đang chứa.

Yêu cầu: 

  • Cho 1 dãy wi. Hỏi có tồn tại 1 dãy thao tác đổ nước để từ trạng thái ban đầu (mỗi bình chứa đầy nước), ta đến được trạng thái mà bình i chứa wi nước.
  • Nếu tồn tại dãy thao tác đổ nước, tìm số lượng thao tác ít nhất.

Input

Dòng đầu: số lượng test T (T <= 20).

Mỗi test gồm:

  • 1 dòng trống
  • 1 dòng chứa số nguyên dương n (n <= 4).
  • 1 dòng chứa n số oi, với 1 <= oi <= 49.
  • 1 dòng chứa n số wi, với 1 <= wi <= oi.

Output

Nếu tồn tại 1 dãy thao tác, in ra số thao tác ít nhất, ngược lại in ra NO.

Ví dụ

Input:
2

3
3 5 5
0 0 4

2
20 25
10 16

Output:
6
NO


  • Người up: thanhvy
  • Nguồn bài: 3rd Polish Olympiad in Informatics, stage 1