문제
N명의 각 선수들의 체중이 주어졌을 때, 주어진 평균에 일치하는 조합으로 선수를 선발하는 프로그램을 작성하자. 다시 말해서 몇 명의 사람이 되었던, 선발된 모든 선수의 체중의 합의 평균이 주어진 값에 정확히 일치해야한다.
단, 전제조건이 있는데, 명수가 몇 명이 되었든, 승리를 위해서 최대한 무거운 사람이 들어가게끔 선수를 선발해야한다.
입력
입력의 첫 번째 줄에는 태권도 선수들의 명수 N(1≤N≤50)이 주어진다.
그 다음 줄에는 태권도 선수들의 체중이 주어지며, 이는 1이상 200이하의 정수이다.
마지막 줄에는 일치해야하는 평균이 주어지며, 이는 1이상 200이하의 정수이다.
출력
문제 제약조건을 만족하는 선발 중 해당 조합 중에서 가장 무거운 사람의 무게를 출력한다. 출력 되는 값은 가능한 조합 중에서 최대가 되어야 한다.
문제 제약조건을 만족하지 못할 경우 -1을 출력한다.
예제
3
80 90 100
90
100
힌트
출처
Online Contest
로그인해야 코드를 작성할 수 있어요.