Hide

Problem F
Dream Team

/problems/dreamteam/file/statement/en/img-0001.png
Jiro Horikoshi

Jiro Horikoshi is a young aircraft designer who is looking to create a team of aircraft engineers to help him design his first airplane. He wants to build a dream team of $12$ engineers. There are $N$ engineers that he can choose from, where the $i$-th engineer has a skill rating $a_i$ and a salary $s_i$. In order to promote a harmonious team enviornment, Jiro wants all the team members to be relatively equally skilled and equally paid. That is, the skill gap cannot exceed $P$ and the pay gap cannot exceed $Q$. As Jiro cannot spend too much (this being his first aircraft), can you help Jiro build the cheapest engineering team that would satisfy the requirement?

Input

The first line of the input contains three space-separated integers $N \: (1 \leq N \leq 100), P \: (1 \leq P \leq 100)$, and $Q \: (1 \leq Q \leq 10^8)$, representing the number of engineers to choose from, the maximum skill gap, and the maximum pay gap, respectively.
The next line will contain $N$ integers $a_1, a_2, \dots a_N \: (1 \leq a_i \leq 100)$, with each $a_i$ representing the skill rating for engineer $i$.
The last line will contain $N$ integers $s_1, s_2, \dots s_N \: (1 \leq s_i \leq 10^8)$, with each $s_i$ representing the salary for engineer $i$.

Output

If there exists a team that satisfy the requirement, output “YES” on the first line and the cost of the cheapest team on the second line. Otherwise, only output “NO” on a single line.

Sample Input 1 Sample Output 1
5 5 100
1 2 3 4 5
100 88 49 10000 666
NO
Sample Input 2 Sample Output 2
12 11 100
2 4 3 1 8 7 12 5 6 11 10 9
40 50 30 10 80 70 20 10 10 10 10 10
YES
350

Please log in to submit a solution to this problem

Log in