Class Division
题号：NC17497
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

There are n students in a school. The final exams are over and the results are out. Student i scored si points in the final exam.

You are the principal of the school and you want to divide the students into m classes. The i-th class should contain at least li students and at most ri students. Each student must belong to exactly one class.

The score of a class is defined as the average scores of all the students in the class. The score of the school is the sum of the scores of all classes. Your task is to find the maximum possible score of the school.

输入描述:

The first line contains a single integer n (1 ≤ n ≤ 250), denoting the number of students.

The next line contains n space-separated integers, s1, s2, ..., sn (1 ≤ si ≤ 106).

The next line contains a single integer m (1 ≤ m ≤ 30), denoting the number of classes.

The next m lines contains two space-separated integers each, li, ri, describing the i-th class.

It is guaranteed that the input is chosen such that there exist a way to assign all the students into classes.

输出描述:

Print the only number — the answer for the problem. Your answer is considered correct if its absolute or relative error does not exceed 10-6.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if .
示例1

输入

复制 
5
3 6 1 2 5
3
1 3
1 1
2 3

输出

复制 
13.0000000000

说明

The optimal strategy is to assign the students with scores 1, 2, 3 into the third class, assign the student with score 5 into the first class and assign the student with score 6 into the second class. Then, the scores of the classes are 5, 6, \frac{1 + 2 + 3}{3} = 2 respectively. The score of the school is 5 + 6 + 2 = 13.