题目内容

小红最近准备整个水果店，需要进 $n$ 件水果。

第 $i$ 件水果在1号批发市场需要 $a_i$ 的价格，在2号批发市场需要 $b_i$ 的价格。

现在市场还在推行一种新的批发模式，一次性批发 $n$ 件水果。

现在，小红想问你，在这三种批发选择下，他批发这 $n$ 件水果花费的最低价格是多少。

输入描述

第一行，两个整数 $n(1\leq n\leq 10^5)$ 和 $m(1\leq m\leq 10^9)$ ，表示需要进的水果件数和在新的批发模式下，一次性批发 $n$ 种水果的价格 $m$ 。

第二行，$n$ 个整数，第 $i$ 个整数 $a_i(1\leq a_i\leq 10^4)$ 表示第 $i$ 件水果在1号批发市场的价格。

第三行，$n$ 个整数，第 $i$ 个整数 $b_i(1\leq b_i\leq 10^4)$ 表示第 $i$ 件水果在2号批发市场的价格。

输出描述

一个整数，表示在这三种批发选择下，小红批发这 $n$ 件水果花费的最低价格。

样例

输入

4 7
1 2 3 4
4 3 2 1

输出

6

说明

第1和2件商品选择1号批发市场，第3和4件商品选择2号批发市场，总价格为 $6$ ，一次性批发的价格为 $7$ ，所以答案为 $6$ 。

思路：贪心

根据题意，一次性批发和单独批发是独立的，所以我们需要计算这两种方式哪种价格更低即可。

对于单独批发，每件水果一定是从价格更低的批发市场购买，所以取 min 即可。

时间复杂度：$O(n)$