Minimum time to make Pizzas.

Author: Efat Sikder

Problem Setter: Efat Sikder

Member, IUBAT IITS Programming Club

Mr. Griffin, the proprietor of a thriving pizza shop in Bangladesh, has enlisted the services of several skilled workers. He's assembled a team of N dedicated workers, each possessing their own unique pizza-making speed denoted by "Ai" the time it takes for them to complete a pizza.


As Mr. Griffin's pizzeria garners increasing popularity, he's keen on optimizing the order fulfillment process. He already knows the exact volume of orders he'll receive each day. To ensure maximum efficiency, he's turned to you, a proficient programmer, to craft a program that can ascertain the minimum time needed to complete all the pizza orders.


Your task is to create a program that will precisely calculate the shortest possible time required to fulfill all the pizza orders.

Input Format


  • ⮞ The first line should specify the number of workers, N (1 ≤ N ≤ 105).
  • ⮞ The second line should contain a list of integers representing the time each worker takes to make a pizza (Ai values) (1 ≤  Ai ≤ 105).
  • ⮞ The third line should indicate the total number of pizza orders P to be fulfilled (1 ≤  P ≤ 106).


Output Format

Print the minimum time required for completing all orders.

Print a new line after every testcase.

Samples

Input
4 5 3 2 8 9
Output
9
Input
6 2 4 5 7 2 1 15
Output
7
Limits
Language Time Memory
GNU C 11 1s 32MB
GNU C++ 14 1s 32MB
GNU C++ 11 1s 32MB
Statistics
Login To Submit