#A0203. 点外卖

点外卖

题目描述

33DAI 肚子饿了,于是在“饱了么”外卖平台点了一份 nn 元的黄焖鸡米饭。在付款时,33DAI 可以从店家提供的三个满减红包中选择一个可用红包使用。

  • 第一个红包可以在金额大于等于 a1a_1 元时使用,可以提供 b1b_1 元的优惠(即总价减少 b1b_1 元)。
  • 第二个红包可以在金额大于等于 a2a_2 元时使用,可以提供 b2b_2 元的优惠(即总价减少 b2b_2 元)。
  • 第三个红包可以在金额大于等于 a3a_3 元时使用,可以提供 b3b_3 元的优惠(即总价减少 b3b_3 元)。

请问 33DAI 怎么选择可以使得最终付款最少。

输入格式

第一行一个整数 nn

接下来三行,每行两个正整数,分别是 a1,b1,a2,b2,a3,b3a_1,b_1,a_2,b_2,a_3,b_3

输出格式

输出一行一个正整数,即 33DAI 最少花费的钱。

33
20 15
30 10
50 49
18
33
40 1
40 2
40 3
33

样例解释

33DAI 满足前两个红包的使用规则,选择第一个红包优惠最多,最后付款 3315=1833-15=18 元。

数据规模与约定

对于 100%100\% 的数据,保证:

  • 1n,a1,b1,a2,b2,a3,b31041\le n,a_1,b_1,a_2,b_2,a_3,b_3 \le 10^4
  • a1b1a_1\ge b_1a2b2a_2\ge b_2a3b3a_3\ge b_3
  • nb1n\ge b_1nb2n\ge b_2nb3n\ge b_3

子任务划分:

  • 子任务 1(30 分):保证 n<a1n\lt a_1n<a2n\lt a_2n<a3n\lt a_3
  • 子任务 2(30 分):保证 b1=b2=b3b_1=b_2=b_3
  • 子任务 3(40 分):没有特殊限制。