All Tracks Problem

The Wars to Come
/

Medium-Hard

Problem
Editorial
Analytics

You have a part to play in the Wars to Come.

As everyone knows, Lord Stannis Baratheon (First of His Name, King of the Andals and the First Men, Lord of the Seven Kingdoms and Protector of the Realm) is one true king. Now, he wants to conquer the North. To conquer, he needs to expand his army. And since, Winter is coming he is impatient. So, he wants the Wildlings to join his army. But, he doesn't want all the wildlings to join. He wants to minimize the number of wildilings in his army, and get the strength that he needs.

The Lord wants you to find the minimum number of wildlings he must recruit to get the strength that he desires. He assures you that you will be knighted if you help him.

There are N wildlings in the Wall (the ones that the Lord can recruit). You are given the strength of all the Wildlings. You are also given the minimum strength that the Lord demands from the Wildlings. Output the minimum number of Wildlings that are to be recruited.

Input:

The first Line contains an integer N denoting the Number of wildlings.

Second Line contains N integers denoting strength of each wildling.

Third Line contains an integer S denoting the minimum strength the Lord demands.

Constraints:

1 <= N <= 1000

1 <= x <= 100 ; x - strength of a wildling

1 <= S <= 10000

Examples:

Input:

8

1 2 3 4 5 3 2 1

10

Output:

3

Input:

2

98 78 17

100

Output:

2

Note: As, Stannis Baratheon ( First of His Name ... ) has the blessings of The Lord of The Light (thanks to his friend Melisandre), it is always possible that he gets the strength that he demands from the wildlings.


SAMPLE INPUT
5
4 7 8 6 4 
10
SAMPLE OUTPUT
2
Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?