Harryxun/stf_run huggingface dataset:
h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)

dp = [float("inf")] * (h + 1010)
dp[0] = 0

for i in range(h + 1):
    for j in range(n):
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
print(min(dp[h:]))


### FIXED CODE ###

h, n = map(int, input().split())
a = []
b = []
for i in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)

dp = [float("inf")] * (h + 10010)
dp[0] = 0

for i in range(h + 1):
    for j in range(n):
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])
print(min(dp[h:]))
s, w = [int(s) for s in intput().split(" ")]
if w >= s:
  print("unsafe")
else:
  print("safe")

### FIXED CODE ###

s, w = [int(s) for s in input().split(" ")]
if w >= s:
  print("unsafe")
else:
  print("safe")
#!/usr/bin/env python3
import sys
import numpy as np
import itertools


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    l = [i for i in range(1,M+1)]
    A = []
    if N==M:
        A.append(l)
    else:
        for v in itertools.permutations(l, N):
            if sorted(v) not in A:
                A.append(sorted(v))

    ans = [0] * len(A)

    for i in range(len(A)):
        #print(A[i])
        for j in range(Q):
            #print(a[j],b[j],c[j],d[j],A[i][b[j]-1]-A[i][a[j]-1], c[j], d[j])
            #print(A[i][b[j]-1]-A[i][a[j]-1], c[j])
            if (A[i][b[j]-1]-A[i][a[j]-1])==c[j]:
                ans[i] += d[j]
        #print(ans[i])
    #print(ans)
    print(max(ans))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
from itertools import *


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    l = [i for i in range(1,M+1)]
    ans = 0
    for v in combinations_with_replacement(l, N):
        score = 0
        for j in range(Q):
            #print(a[j],b[j],c[j],d[j],A[i][b[j]-1]-A[i][a[j]-1], c[j], d[j])
            #print(A[i][b[j]-1]-A[i][a[j]-1], c[j])
            if (v[b[j]-1]-v[a[j]-1])==c[j]:
                score += d[j]
        #print(ans[i])
        ans = max(ans, score)
    #print(ans)
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    a = [int()] * (Q)  # type: "List[int]"
    b = [int()] * (Q)  # type: "List[int]"
    c = [int()] * (Q)  # type: "List[int]"
    d = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    def main():
        N, M = map(int, input().split())
        S = str(input())
        T = str(input())

        lcm = N * M // math.gcd(N, M)

        lcm2 = (lcm // N) * (lcm // M) // math.gcd((lcm // N), (lcm // M))
        i = 0
        while True:
            while lcm2 * i < min(N, M):
                if S[lcm2 * i // (lcm // N)] != T[lcm2 * i // (lcm // M)]:
                    return -1
                i += 1
            else:
                return lcm

    print(main())


resolve()

### FIXED CODE ###

import fractions
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    def main():
        N, M = map(int, input().split())
        S = str(input())
        T = str(input())

        lcm = N * M // fractions.gcd(N, M)
        NN = lcm // N
        MM = lcm // M

        lcm2 = NN * MM // fractions.gcd(NN, MM)
        i = 0
        ans = lcm
        while True:
            if lcm2 * i // NN < N and lcm2 * i // MM < M:
                if S[lcm2 * i // NN] != T[lcm2 * i // MM]:
                    ans = -1
                i += 1
            else:
                return ans

    print(main())


resolve()
A=list(map(lambda x: (int(x), False), input().split()))
A+=list(map(lambda x: (int(x), False), input().split()))
A+=list(map(lambda x: (int(x), False), input().split()))

N = int(input())
for _ in range(N):
  n = int(input())
  for a, b in A:
    if a == n:
      b = True
if (A[0][1] and ((A[1][1] and A[2][1]) or \
                       (A[3][1] and A[6][1]) or \
                       (A[4][1] and A[8][1])) or \
          (A[1][1] and A[4][1] and A[7][1]) or \
          (A[2][1] and A[5][1] and A[8][1]) or \
          (A[3][1] and A[4][1] and A[5][1]) or \
          (A[6][1] and A[7][1] and A[8][1]) or \
          (A[2][1] and A[4][1] and A[6][1]):
    print("YES")
else:
    print("No")


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: "List[List[int]]", N: int, b: "List[int]"):
    A_ = []
    for a_ in A:
        A_ += [[a__, False] for a__ in a_]
    for b_ in b:
        for a__ in A_:
            if a__[0] == b_:
                a__[1] = True
    if (A_[0][1] and ((A_[1][1] and A_[2][1]) or \
                        (A_[3][1] and A_[6][1]) or \
                        (A_[4][1] and A_[8][1]))) or \
            (A_[1][1] and A_[4][1] and A_[7][1]) or \
            (A_[2][1] and A_[5][1] and A_[8][1]) or \
            (A_[3][1] and A_[4][1] and A_[5][1]) or \
            (A_[6][1] and A_[7][1] and A_[8][1]) or \
            (A_[2][1] and A_[4][1] and A_[6][1]):
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = [[int(next(tokens)) for _ in range(3)] for _ in range(3)]  # type: "List[List[int]]"
    N = int(next(tokens))  # type: int
    b = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(A, N, b)

if __name__ == '__main__':
    main()
import sys, re, os
    from collections import deque, defaultdict, Counter
    from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
    from itertools import permutations, combinations, product, accumulate
    from operator import itemgetter, mul
    from copy import deepcopy
    from string import ascii_lowercase, ascii_uppercase, digits
    from fractions import gcd
     
    def input(): return sys.stdin.readline().strip()
    def INT(): return int(input())
    def MAP(): return map(int, input().split())
    def S_MAP(): return map(str, input().split())
    def LIST(): return list(map(int, input().split()))
    def S_LIST(): return list(map(str, input().split()))
     
    sys.setrecursionlimit(10 ** 9)
    INF = float('inf')
    mod = 10 ** 9 + 7
     
    N = INT()
    A = LIST()
     
    max_length = len("{:b}".format(max(A)))
     
    cnt = [defaultdict(int) for _ in range(max_length)]
     
    for i in range(N):
        num = "{:b}".format(A[i]).zfill(max_length)
        for j in range(len(num)):
            # [i桁目][numのj番目の数，(0 or 1)]
            # 0, 1 の数を数える
            cnt[max_length-1-j][num[j]] += 1
     
    ans = 0
     
    for i in range(max_length):
        # 1を左にiシフト(2 ** i 倍)
        # 桁内で0の個数 * 桁内で1の個数 が，XOR = 1になる数 (0 xor 1 = 1)
        ans = ans + (1 << i) * cnt[i]["0"] * cnt[i]["1"]
    ans = ans % mod
    print(ans)
     
     
     

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N = INT()
A = LIST()
 
max_length = len("{:b}".format(max(A)))
 
cnt = [defaultdict(int) for _ in range(max_length)]
 
for i in range(N):
    num = "{:b}".format(A[i]).zfill(max_length)
    for j in range(len(num)):
        # [i桁目][numのj番目の数，(0 or 1)]
        # 0, 1 の数を数える
        cnt[max_length-1-j][num[j]] += 1
 
ans = 0
 
for i in range(max_length):
    # 1を左にiシフト(2 ** i 倍)
    # 桁内で0の個数 * 桁内で1の個数 が，XOR = 1になる数 (0 xor 1 = 1)
    ans = ans + (1 << i) * cnt[i]["0"] * cnt[i]["1"]
ans = ans % mod
print(ans)
WALL = 100
w, h = map(int,input().split())
lst = [[WALL] + list(map(int,input().split())) + [WALL] for i in range(h)]
lst.insert(0, [WALL] * (w + 2))
lst.append([WALL] * (w + 2))

visited = [[0] * (w + 2) for _ in range(h + 2)]
hold = []

def search(x, y):

  if lst[x][y] == WALL:
    visited[x][y] = 3
    return 3

  if lst[x][y] == 1:
    visited[x][y] = 2
    return 2

  visited[x][y] = 1
  hold.append((x, y))

  if not x % 2:
    pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
  else:
    pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
  
  ret = 0
  for t in pairs:
    tx, ty = t[0], t[1]
    a = 0
    if not visited[tx][ty]:
      a = search(tx, ty)
    elif visited[x][y] == 3:
      a = 3
    elif visited[x][y] == 2:
      a = 2
    if a > ret:
      ret = a

  return ret

for x in range(1, h + 1):
  for y in range(1, w + 1):
    if not visited[x][y] and not lst[x][y]:
      stat = search(x, y)
      for point in hold:
        visited[point[0]][point[1]] = stat
      hold.clear()

ans = 0
for x in range(1, h + 1):
  for y in range(1, w + 1):
    if lst[x][y]:
      if not x % 2:
        pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
      else:
        pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
      for t in pairs:
        tx, ty = t[0], t[1]
        if visited[tx][ty] in [0,3]:
          ans += 1

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

WALL = 100
w, h = map(int,input().split())
lst = [[WALL] + list(map(int,input().split())) + [WALL] for i in range(h)]
lst.insert(0, [WALL] * (w + 2))
lst.append([WALL] * (w + 2))

visited = [[0] * (w + 2) for _ in range(h + 2)]
hold = []
app = hold.append

def search(x, y):

  if lst[x][y] == WALL:
    visited[x][y] = 3
    return 3

  if lst[x][y] == 1:
    visited[x][y] = 2
    return 2

  visited[x][y] = 1
  app((x, y))

  if not x % 2:
    pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
  else:
    pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
  
  ret = 0
  for t in pairs:
    tx, ty = t[0], t[1]
    v = visited[tx][ty]
    a = 0
    if not v:
      a = search(tx, ty)
    elif v == 3:
      a = 3
    elif v == 2:
      a = 2
    if a > ret:
      ret = a
  return ret

def main():

  for x in range(1, h + 1):
    for y in range(1, w + 1):
      if not visited[x][y] and not lst[x][y]:
        stat = search(x, y)
        for point in hold:
          visited[point[0]][point[1]] = stat
        hold.clear()
  
  ans = 0
  for x in range(1, h + 1):
    for y in range(1, w + 1):
      if lst[x][y]:
        if not x % 2:
          pairs = [(x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y - 1), (x + 1, y)]
        else:
          pairs = [(x - 1, y), (x - 1, y + 1), (x, y - 1), (x, y + 1), (x + 1, y), (x + 1, y + 1)]
        for t in pairs:
          tx, ty = t[0], t[1]
          if (visited[tx][ty] in [0,3]) and (lst[tx][ty] in [WALL, 0]):
            ans += 1
  
  print(ans)

main()
N = input()
P = list(map(int, input().split()))
sort_P = sorted(P)
new_P = []
for idx, p in enumerate(P):
    new_P.append(sort_P[idx] - p)
new_new_P = set(new_P)
new_new_P.remove(0)
if len(new_new_P) > 2:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

N = input()
P = list(map(int, input().split()))
flag = 0
for idx, p in enumerate(P):
    if p != idx + 1:
        flag += 1

if flag > 2:
    print("NO")
else:
    print("YES")
x,y = map(int,input().split)

print(x*y - x - y +1)

### FIXED CODE ###

x,y = map(int,input().split())

print(x*y - x - y +1)
# -*- coding: utf-8 -*-
import numpy as np
import math
 
N, M = map(int, input().split())
 
def comb(n, r):
    return int(math.factorial(n) / (math.factorial(n - r) * math.factorial(r)))
  
print(comb(N, 2)+comb(M, 2))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import math
 
N, M = map(int, input().split())
 
def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
print(comb(N, 2)+comb(M, 2))
import math
A = int(input())
ans = int(input())
for i in range(A-1):
    B = int(input())
    ans = B * ans // math.gcd(ans,B)
print(ans)

### FIXED CODE ###

import fractions
A = int(input())
ans = int(input())
for i in range(A-1):
    B = int(input())
    ans = B * ans // fractions.gcd(ans,B)
print(ans)
import collections

n = int(input())
a = list(map(int,input().split()))
a1 = collections.Counter(a[0::2]).most_common()
a2 = collections.Counter(a[1::2]).most_common()
#a1.append((0,0))
#a2.append((0,0))
print(a1)
print(a2)

if a1[0] != a2[0]:
    print(n-a1[0][1]-a2[0][1])
else:
    print(min(n-a1[0][1]-a2[1][1],n-a1[1][1]-a2[0][1]))



### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
a1 = collections.Counter(a[0::2]).most_common()
a2 = collections.Counter(a[1::2]).most_common()
a1.append((0,0))
a2.append((0,0))
#print(a1)
#print(a2)

if a1[0] != a2[0]:
    print(n-a1[0][1]-a2[0][1])
else:
    print(min(n-a1[0][1]-a2[1][1],n-a1[1][1]-a2[0][1]))
n=int(input())
a=[[]*3 for ii in range(n)]
for ii in range(n):
  s=input().split()
  a[ii][0]=s[0]
  a[ii][1]=-int(s[1])
  a[ii][2]=ii
a.sort()
for ii in range(n):
  print(a[ii][2]+1)

### FIXED CODE ###

n=int(input())
a=[[""]*3 for ii in range(n)]
for ii in range(n):
  s=input().split()
  #print(s)
  a[ii][0]=s[0]
  a[ii][1]=100-int(s[1])
  a[ii][2]=ii
a.sort()
for ii in range(n):
  print(a[ii][2]+1)
from bisect import bisect_left
N = int(input())
X = list(map(int,input().split()))
Y = X.copy()
Y.sort()
for i in range(N):
    k = bisect_left(Y,X[i])
    if k < N//2:
        print(Y[N//2])
    else:
        print(Y[N//2-1])


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
X = list(map(int,input().split()))
Y = X.copy()
Y.sort()
for i in range(N):
    k = bisect_left(Y,X[i])
    if k < N//2:
        print(Y[N//2])
    else:
        print(Y[N//2-1])
import sympy
N = int(input())
count = 0
for C in range(1, N):
    AB = N - C
    count = count + len(sympy.divisors(AB))
print(count)

### FIXED CODE ###

N = int(input())
count = 0
for i in range(1, N):
    count += (N-1) // i
print(count)
from itertools import groupby
H, W = map(int, input().split())
if H<=6:
    assert False
S = ["" for _ in range(W)]
T = []
for _ in range(H):
    s = input()
    T.append(s)
    for i, c in enumerate(s):
        S[i] += c
T = [sorted(t) for t in T]
S = [sorted(s) for s in S]
T.sort()
S.sort()
cnt = 0
for _, g in groupby(T):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(S):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
print("YES")


### FIXED CODE ###

# この解法は嘘を含む

from itertools import groupby
H, W = map(int, input().split())
S_ = ["" for _ in range(W)]
T_ = []
for _ in range(H):
    s = input()
    T_.append(s)
    for i, c in enumerate(s):
        S_[i] += c
T = [sorted(t) for t in T_]
S = [sorted(s) for s in S_]
cnt = 0
for _, g in groupby(sorted(T)):
    if len(list(g))%2:
        cnt += 1
if H%2 < cnt:
    print("NO")
    exit()
cnt = 0
for _, g in groupby(sorted(S)):
    if len(list(g))%2:
        cnt += 1
if W%2 < cnt:
    print("NO")
    exit()
if W%2 or H%2:
    print("YES")
    exit()
T1 = []
T2 = []
for i, (_, t) in enumerate(sorted(zip(T, T_))):
    if i%2:
        T1.append(t)
    else:
        T2.append(t)
T_p = T1 + T2[::-1]
S_pp = ["" for _ in range(W)]
for t in T_p:
    for i, c in enumerate(t):
        S_pp[i] += c
S1 = []
S2 = []
for i, (_, s) in enumerate(sorted(zip(S, S_pp))):
    if i%2:
        S1.append(s)
    else:
        S2.append(s)
S_p = S1 + S2[::-1]
for s1, s2 in zip(S_p, S_p[::-1]):
    for c1, c2 in zip(s1, s2[::-1]):
        if c1!=c2:
            print("NO")
            exit()
print("YES")
/*
 * b.cpp
 *
 *  Created on: 2017/08/21
 *      Author: pinebooks
 */

#include <iostream>
#include <string>

using namespace std;

int main(void){
	string s;
	cin >> s;
	for (char c = 'a'; c < 'z'; c++) {
		bool found = false;
		for (int i=0; i<s.length(); i++){
			if (s[i] == c)
				found = true;
		}
		if(!found){
			cout << c << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}

### FIXED CODE ###

from collections import Counter
S = input()

counter = dict(Counter(S))
counter = sorted(counter) 
alphabets = "abcdefghijklmnopqrstuvwxyz"

found = False
for letter in alphabets:
    if letter in counter:
        continue
    else:
        found = True
        print(letter)
        break

if found is not True:
    print("None")
k = int(input())
s = input()

print(s if len(s)<=k else s[0:k] + "...")a

### FIXED CODE ###

k = int(input())
s = input()

print(s if len(s)<=k else s[0:k] + "...")
import itertools
import collections
n=int(input())
X=[]
for i in range(n):
  X.append([int(i) for i in input().split()])
X.sort(key=lambda x:(x[0],x[1]))
Y=[]
for c in itertools.combinations(range(n),2):
  x1,y1,x2,y2=X[c[0]][0],X[c[0]][1],X[c[1]][0],X[c[1]][1]
  Y.append((x2-x1,y2-y1))
yy=collections.Counter(Y)
print(n-yy.most_common()[0][1])

### FIXED CODE ###

import itertools
import collections
n=int(input())
X=[]
for i in range(n):
  X.append([int(i) for i in input().split()])
X.sort(key=lambda x:(x[0],x[1]))
Y=[]
for c in itertools.combinations(range(n),2):
  x1,y1,x2,y2=X[c[0]][0],X[c[0]][1],X[c[1]][0],X[c[1]][1]
  Y.append((x2-x1,y2-y1))
yy=collections.Counter(Y)
print(1 if n==1 else n-yy.most_common()[0][1])
x = int(input())

dp=[float('inf')]*(x+1)
dp[0]=0
for i in range(1,x+1):
    for j in range((i-1)*i//2+1):
        if j<=x and i+j<=x:
            dp[i+j]=min(dp[i+j],i)
print(dp[x])

### FIXED CODE ###

x = int(input())

ans=0
y=0
for i in range(1,x+1):
    y=y+i
    ans+=1
    if y>=x:
        print(ans)
        break
S = int(input())

h = S//3600
m = (S//60)-(S//3600)
s = S//60
print(h':'m':'s)





### FIXED CODE ###

S = int(input())
h = S//3600
m = (S//60)-60*(S//3600)
s = S%60
print('{}:{}:{}'.format(h,m,s))
S = input()
def kaibun(st):
    stre = st[::-1]
    if st == stre:
        return 1
    else:
        return 0

if kaibun(S[0:(len(S)-1) // 2]) and kaibun(S) and kaibun(S[(len(S)+3) // 2]):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

S = input()
def kaibun(st):
    stre = st[::-1]
    if st == stre:
        return 1
    else:
        return 0

if kaibun(S[0:(len(S)-1) // 2]) and kaibun(S) and kaibun(S[(len(S)+3) // 2-1:len(S)]):
    print("Yes")
else:
    print("No")
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
Vs = list(mapint())
Vs.sort(reverse=True)
from collections import defaultdict, Counter
from scipy.special import comb

count = defaultdict(int)
c = Counter(Vs)
ans = 0
for i in range(A, B+1):
    val = sum(Vs[:i])/i
    if val>=ans:
        ans = val
        lowest_cnt = 0
        lowest = Vs[i-1]
        for j in range(i):
            if Vs[j]==lowest:
                lowest_cnt += 1
        count[int(ans*2)] += comb(c[lowest], lowest_cnt)

print(ans)
print(count[int(ans*2)])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
Vs = list(mapint())
Vs.sort(reverse=True)
from collections import defaultdict, Counter
from math import factorial, gcd

count = defaultdict(int)
c = Counter(Vs)
ans = 0
ans_2 = (0, 0)
for i in range(A, B+1):
    val = sum(Vs[:i])
    if val/i>=ans-0.000000000000001:
        ans = val/i
        lowest_cnt = 0
        lowest = Vs[i-1]
        for j in range(i):
            if Vs[j]==lowest:
                lowest_cnt += 1
        val, i = val//gcd(val, i), i//gcd(val, i)
        count[(val, i)] += factorial(c[lowest])/factorial(lowest_cnt)/factorial(c[lowest]-lowest_cnt)
        ans_2 = (val, i)

print(ans)
print(round(count[ans_2]))