Background

小红在孤儿院的朋友们喜欢玩偶，但是没有能力去购买，小红很伤心，她想达成朋友们的心愿。

过了很久很久，小红终于存够了零花钱了，她很开心，因为终于可以买玩偶了。

商店里一共有 3 种不同的玩偶大礼包，每款大礼包中玩偶的数量不同，当然价格也各不相同。

小红想买 n 个玩偶分别送给 n 个同她一样喜欢玩偶的好朋友，

但是每个礼包中玩偶的个数可能不一样，可能要购买超过 n 数量的玩偶才够分配给 n 个朋友。

她决定只购买一种类型的大礼包！商店中的所有类型的大礼包数量充足。

请问至少要花多少钱她才可以达成把玩偶分配给朋友的心愿。

Description

请问至少要花多少钱她才可以达成把玩偶分配给朋友的心愿。

Format

Input

第一行包含一个正整数 n，表示需要玩偶的数量。

接下来三行，每行用 2 个正整数描述一种包装的玩偶：

其中第 1 个整数表示这种大礼包内玩偶的数量，第 2 个整数表示这种大礼包的价格。

保证所有的 7 个数都是不超过 10000 的正整数。

Output

1 个整数，表示 小红 最少需要花费的钱。

Sample 1

Input

57
2 2
50 30
30 27

Output

54

Source

Vijos Original