题目背景

你是小镇的守卫队长,守护镇子是职责所在。这天镇外出现了一条长着 $n$ 颗头颅的巨蛇,四处喷火捣乱,你心急如焚。幸好一支佣兵团恰好路过,团里有 $m$ 位佣兵可以雇佣。

题目描述

每位佣兵最多只能砍掉一颗大小不超过 $z_i$ 的头颅,雇佣他需要支付 $z_i$ 枚金币。求砍掉巨蛇所有头颅的最小总花费。

输入格式

第一行两个整数 $n$,$m$。

下接 $n$ 行,第 $i$ 行一个整数 $a_i$,表示第 $i$ 颗头颅的大小。

下接 $m$ 行,每行一个整数,依次为每位佣兵能砍的头颅大小上限与所需金币数 $z_1, \cdots, z_m$。

输出格式

一个整数,表示最小花费。如果无解,输出 you died!。

样例

2 3
5 
4
7 
8
4

11

提示

对于所有数据,$1 \le n,m \le 2 \times 10^4$,$1 \leq a_i,z_i \leq 10^5$。