[STCD] Tìm Thanh Ngân

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Nhà Thanh Ngân có \(p\) bậc thang đánh số từ \(1\) đến \(p\). Vị trí sàn nhà kề với cầu thang được tính là bậc thang \(0\). Ngọc Thịnh đang ở bậc thang \(0\) và Thanh Ngân ở bậc thang \(p\). Ngân thách đố Thịnh đến được bậc thang \(p\) chỉ bằng cách bước theo ràng buộc của Ngân:

  • Nếu Thịnh đang đứng ở bậc thang \(i\), Thịnh chỉ có thể bước lên một trong các bậc thang \(i+a_1\), \(i+a_2\),..., \(i+a_n\).
  • Thịnh không được phép bước đến các bậc thang \(b_1\), \(b_2\),..., \(b_m\).
  • Thịnh cũng không được phép bước lùi về một hoặc nhiều bậc thang thấp hơn vị trí của mình.

Cho biết trước các giá trị \(p\), \(n\), \(m\) và hai dãy số nguyên dương \(a_1\), \(a_2\),..., \(a_n\), \(b_1\), \(b_2\),..., \(b_m\). Bạn hãy lập trình giúp Thịnh xác định xem liệu cậu ấy có bước đến được bậc thang \(p\) để gặp Ngân không nhé.


Input

Dòng đầu chứa số nguyên dương \(n\) \((1\leq n\leq 10)\).

Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_n\) \(\left(1\leq a_1 < a_2 < ... < a_n \leq 10^5\right)\).

Dòng tiếp theo chứa số nguyên dương \(m\) \(\left(1\leq m\leq 10^5\right)\).

Dòng tiếp theo chứa \(m\) số nguyên dương \(b_1\), \(b_2\),..., \(b_m\) \(\left(1\leq b_1 < b_2 < ... < b_m < p \leq 10^5\right)\).

Dòng cuối cùng chứa số nguyên dương \(p\).


Output

In ra Yes nếu Thịnh có thể bước từ bậc thang \(0\) đến bậc thang \(p\) để gặp Thanh Ngân. Ngược lại, in ra No.


Ví dụ

Sample input 1
3
3 4 5
4
4 5 6 8
15
Sample output 1
Yes
Giải thích

Thịnh có thể lần lược bước lên các bậc thang \(3\), \(7\), \(12\), và \(15\).

Sample input 2
4
2 3 4 5
4
3 4 5 6
8
Sample output 2
No
Sample input 3
4
2 5 7 8
5
2 9 10 11 19
20
Sample output 3
Yes