Under construction

Still being built. Things may change

Cargo Loading

Time limit2sMemory limit128 MB

Summary
Given crane weight limits and box weights, find the minimum minutes to load all boxes with one box per crane per minute, or -1 if impossible.
Level

Medium5 of 10

Topics
Greedy, Sorting, Two pointers
Solved
No attempts yet

Problem

Jimin works at a harbor and needs to load several boxes onto a cargo ship. There are N cranes at the harbor, and each crane can load one box per minute. All cranes can work at the same time.

Each crane has a weight limit. A crane cannot move a box that is heavier than its limit. Find the minimum time needed to load every box onto the ship.

Input

The first line contains N, the number of cranes. N is a positive integer no greater than 50.

The second line contains the weight limits of the N cranes. Each limit is a positive integer no greater than 1,000,000.

The third line contains M, the number of boxes. M is a positive integer no greater than 10,000.

The fourth line contains the weights of the M boxes. Each weight is a positive integer no greater than 1,000,000.

Output

Print the minimum number of minutes needed to load all boxes onto the ship. If it is impossible to load every box, print -1.

Examples4

  1. Example 1

    Input
    3
6 8 9
5
2 5 2 4 7
    Expected output
    2

  2. Example 2

    Input
    2
19 20
7
14 12 16 19 16 1 5
    Expected output
    4

  3. Example 3

    Input
    4
23 32 25 28
10
5 27 10 16 24 20 2 32 18 7
    Expected output
    3

  4. Example 4

    Input
    10
11 17 5 2 20 7 5 5 20 7
5
18 18 15 15 17
    Expected output
    2