#487 Sum of Adjacent Minimums

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: pk661

Time limit: 1000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

Statement language

You are given positive integers $N, X$ and $C_1, C_2, \cdots, C_N$ . Over all nonnegative real numbers $R_1, R_2, \cdots, R_N$ satisfying $C_1R_1 + C_2R_2 + \cdots + C_NR_N = X$ , find the maximum possible value of

\min(R_1, R_2) + \min(R_2, R_3) + \cdots + \min(R_{N-1}, R_N).

Input

The input is given from Standard Input in the following format:

$N\ X$ $C_1\ C_2\ \cdots\ C_N$

Output

Let $M$ be the maximum value. Print two positive integers $P,Q$ , separated by a space, such that $M=\dfrac{P}{Q}$ .

Constraints

$2 \leq N \leq 3\,000$ .
$1 \leq X \leq 10^9$ .

Subtasks

#	Score	Constraints
1	15	$N=2$ .
2	23	$C_1=C_2=\cdots=C_N$ .

Samples

Sample 1

Input

5 7
8 1 2 1 8

Output

7 2

Sample 2

Input

4 11
2 2 2 2

Output

33 8

Sample 3

Input

2 10
3 7

Output

2026 2026

Editorial

View editorial