Background

As the village chief, it is your duty to defend the village. Today, a dragon has come with $n$ heads, wreaking havoc everywhere. You are anxious. Fortunately, a group of knights has arrived. There are $m$ members in the group.

Problem Description

Each person can cut off at most one head of size not exceeding $z_i$, and it costs $z_i$ coins. Find the minimum total cost.

Input Format

• The first line contains two integers $n$, $m$.
• The next $n$ lines each contain one integer, the size of a head.
• The next $m$ lines each contain one integer $z_i$, the maximum head size the $i$-th person can cut and the number of coins required.

Output Format

Output a single integer, the minimum total cost. If it is impossible, output you died!.

2 3
5 
4
7 
8
4

11

Hint

For all testdata, $1 \le n, m \le 2 \times 10^4$, $1 \le z_i \le 10^5$.

Translated by ChatGPT 5