Một người bán hàng có $n$ mặt hàng để bán cho một người mua duy nhất. Người mua có một hồ sơ định giá $\bar{v} = (v_1, \dots, v_n)$, trong đó $v_j \ge 0$ biểu thị giá trị của cô ấy đối với mặt hàng $j$.

Người bán có thể thiết lập một bảng giá $\bar{p}$, tức là một vectơ giá của các mặt hàng $(p_1, \dots, p_n)$. Với một bảng giá $\bar{p}$, lợi ích của việc mua mặt hàng $j$ là $v_j - p_j$. Người mua sẽ mua một mặt hàng $j$ duy nhất giúp tối đa hóa lợi ích của cô ấy, hoặc không mua gì nếu lợi ích từ việc mua bất kỳ mặt hàng nào đều âm. Nếu có nhiều mặt hàng cùng mang lại lợi ích tối đa, cô ấy sẽ chọn mặt hàng có giá thấp nhất. Doanh thu của người bán được định nghĩa là giá của mặt hàng mà người mua mua, và nếu người mua không mua gì, doanh thu là 0.

Hiện tại chúng ta biết rằng hồ sơ định giá $\bar{v}$ được rút ra từ một phân phối chung $F$ xác định xác suất của mọi giá trị có thể có của $\bar{v}$. Thật không may, chúng ta không biết $F$. Thay vào đó, chúng ta biết các phân phối biên $F_1, F_2, \dots, F_n$: phân phối $F_i$ xác định xác suất $v_i = x$ cho mọi $x$ có thể. Nhưng chúng ta không biết chúng tương quan với nhau như thế nào: các giá trị không nhất thiết phải độc lập, vì vậy các xác suất riêng lẻ của $v_i = x$ và $v_j = y$ không xác định xác suất của cả hai sự kiện xảy ra đồng thời. Lưu ý rằng phân phối chung $F$ là trên hồ sơ định giá $\bar{v}$ và phân phối biên $F_i$ là trên giá trị $v_i$ của mặt hàng $i$.

Với bảng giá $\bar{p}$ và các phân phối biên $F_1, F_2, \dots, F_n$, chúng ta được yêu cầu tính doanh thu kỳ vọng tối thiểu trong số tất cả các phân phối chung có thể. Về mặt hình thức, gọi $\mathcal{F}$ là tập hợp các phân phối chung trên các hồ sơ định giá $\bar{v}$ mà các phân phối biên của chúng đối với các giá trị mặt hàng riêng lẻ chính là $F_1, F_2, \dots, F_n$. Gọi $\text{Rev}(\bar{p}, F)$ là doanh thu kỳ vọng của người bán khi thiết lập bảng giá $\bar{p}$, nếu hồ sơ định giá $\bar{v}$ được rút ra từ một phân phối chung $F$. Chúng ta được yêu cầu tính: $$\min_{F \in \mathcal{F}} \text{Rev}(\bar{p}, F)$$

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^5$), số lượng mặt hàng cần bán.

Dòng thứ hai chứa $n$ số nguyên không âm $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^5$), vectơ giá $\bar{p}$.

$n$ dòng tiếp theo mô tả các phân phối biên $F_1, F_2, \dots, F_n$. Mỗi dòng bắt đầu bằng một số nguyên $k$: kích thước hỗ trợ (số lượng giá trị khác nhau) của $F_i$. Sau đó là $k$ cặp số $q_j$ và $v_j$ ($0 \le q_j \le 1$, $0 \le v_j \le 10^6$), nghĩa là $F_i$ có xác suất $q_j$ để có giá trị $v_j$. Các giá trị $v_j$ có thể được đưa ra dưới dạng số thập phân hoặc ký hiệu khoa học. Đảm bảo rằng $\sum_{j=1}^k q_j = 1$.

Tổng các giá trị của $k$ trên $n$ dòng này sẽ không vượt quá $3 \cdot 10^5$. Tổng kích thước của dữ liệu vào sẽ không vượt quá 5 mebibytes.

Dữ liệu ra

Xuất ra một số thực duy nhất: doanh thu kỳ vọng tối thiểu trong số tất cả các phân phối chung có thể. Câu trả lời của bạn sẽ được coi là đúng nếu và chỉ nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-6}$.

Ví dụ

Ví dụ 1

2
2 5
4 0.254 5 0.227 8 0.269 10 0.25 9
4 0.274 9 0.272 9 0.223 8 0.231 7

2.0000000000

Ví dụ 2

2
7 7
2 0.5 1 0.5 0
2 0.3 5 0.7 1

0.0000000000

Ví dụ 3

1
5
1 1.0 5

5.0000000000