the-wars-to-come-5

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:
3

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

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
n=int(eval(input()))
s=list(map(int,input().split()))
k=int(eval(input()))
#lst=list(s)
s.sort(reverse=True)
#print s[0]
sum=i=c=0
#sum,i,c=0,0,0
while(sum<=k):
	sum+=s[i]
	c+=1
	i+=1
print(c)	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n=eval(input())
l=[int(i) for i in input().split()]
m=eval(input())
l.sort(reverse=True)
s,c=0,0
while(s<=m):
	s+=l[c]
	c+=1
print(c)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n=eval(input())
l=[int(i) for i in input().split()]
m=eval(input())
l.sort(reverse=True)
s,c=0,0
while(s<=m):
	s+=l[c]
	c+=1
print(c)