样例下载

问题描述

一年一度的狂欢节就要到了，Farmer John 准备给他的奶牛们买一些酒进行狂欢。

共有 $n$ 瓶酒出售，第 $i$ 瓶酒的价格是 $a_i$。其中有一些酒正在搞促销活动，以八折价格进行销售（称为特价优惠）。

有 $m$ 种满减优惠方式，满减优惠方式只有在所有酒都不选择特价优惠时才能使用，且最多只可以选择一种满减优惠方式。每种满减优惠描述为 $b_i, c_i$，即满 $b_i$ 减 $c_i$（当消费总额不少于 $b_i$ 时总价优惠 $c_i$）。

现在 John 想一次把这些酒全部买下，但是由于预算有限，他想知道至少需要多少钱（保留两位小数）。

输入格式

第一行包含两个正整数 $n,m$，分别表示要购买的酒的数目与满减优惠的种数。

接下来 $n$ 行，每行包含两个整数 $a_i$ 和一个 $0$ 或 $1$ 的整数，其中 $a_i$ 表示第 $i$ 瓶酒的价格，$1$ 或 $0$ 表示是否有特价优惠（$1$ 表示有，$0$ 表示没有）。

接下来 $m$ 行，每行包含两个整数 $b_i, c_i$，表示一个满减优惠（参见题目描述）。

输出格式

输出只有一行，包含一个浮点数，表示买下所有酒所需的最小钱数（保留两位小数）。

输入输出样例

输入

2 1
6 1
10 1
12 2

输出

12.80

数据规模与约定

对于 $30\%$ 的数据，$n,m,a_i,b_i,c_i\le10$；

对于 $70\%$ 的数据，$n,m\le100$，$a_i,b_i,c_i\le10^5$；

对于 $100\%$ 的数据，$n,m\le100000$，$1\le a_i,b_i,c_i\le10^9$，$b_i>c_i$。