Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Knapsack I
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 1094Accepted: 325

Description

Lambert wants to carry several kinds of items with a knapsack. Items of each kind have integral size and infinite supply. The knapsack also has an integral capacity. Due to some esoteric reasons, an item of any kind can be divided evenly into a fixed number of identical parts. The resulting parts can again be divided, and the process of even division can go on endlessly. Given n kinds of items, can the capacity of the knapsack be fulfilled?

Input

The input contains multiple test cases. Each test case begins with a line containing three positive integers n, x and k (n ≤ 1000, k ≥ 2), where x is the capacity of the knapsack, and k means each division divides an item or a divided part into k identical smaller parts. Then comes a line containing n positive integers, the sizes of different kinds of items.

Output

For each test case, output one line containing “Yes” if the knapsack can be fulfilled or “No” otherwise.

Sample Input

2 3 5
4 11
3 16 2
3 6 9

Sample Output

Yes
No

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator