Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
xyd = [input().split() for _ in range(n)]
xd = [(int(v[0]), 1 if v[2] == 'R' else -1 if v[2] == 'L' else 0) for v in xyd]
yd = [(int(v[1]), 1 if v[2] == 'U' else -1 if v[2] == 'D' else 0) for v in xyd]
def calc(mid):
    xmin = min(x + mid * d for x, d in xd)
    xmax = max(x + mid * d for x, d in xd)
    ymin = min(y + mid * d for y, d in yd)
    ymax = max(y + mid * d for y, d in yd)
    return (xmax - xmin) * (ymax - ymin)
lo = 0.0
hi = 1e100
while hi - lo > 1e-10:
    mid1 = (lo * 2 + hi) / 3
    mid2 = (lo + hi * 2) / 3
    if calc(mid1) > calc(mid2):
        lo = mid1
    else:
        hi = mid2
print(calc((lo + hi) / 2))


### FIXED CODE ###

n = int(input())
m = {}
for _ in range(n):
    x, y, d = input().split()
    x, y = int(x) * 2, int(y) * 2
    if d not in m:
        m[d] = [1000000000, -1000000000, 1000000000, -1000000000]
    m[d][0] = min(m[d][0], x)
    m[d][1] = max(m[d][1], x)
    m[d][2] = min(m[d][2], y)
    m[d][3] = max(m[d][3], y)

dx = {'L': -1, 'R': 1, 'U': 0, 'D': 0}
dy = {'L': 0, 'R': 0, 'U': 1, 'D': -1}

px = []
py = []
for d in 'LRUD':
    if d in m:
        px.append((m[d][0], dx[d]))
        px.append((m[d][1], dx[d]))
        py.append((m[d][2], dy[d]))
        py.append((m[d][3], dy[d]))

times = [0]
def append(pa, pb):
    (a, da) = pa
    (b, db) = pb
    if db != da:
        t = (a - b) // (db - da)
        if t >= 0:
            times.append(t)

for i in range(len(px)):
    for j in range(i + 1, len(px)):
        append(px[i], px[j])

for i in range(len(py)):
    for j in range(i + 1, len(py)):
        append(py[i], py[j])

ret = 1000000000000000000
for t in times:
    bb = [1000000000, -1000000000, 1000000000, -1000000000]
    for d in 'LRUD':
        if d in m:
            bb[0] = min(bb[0], m[d][0] + dx[d] * t)
            bb[1] = max(bb[1], m[d][1] + dx[d] * t)
            bb[2] = min(bb[2], m[d][2] + dy[d] * t)
            bb[3] = max(bb[3], m[d][3] + dy[d] * t)
    ret = min(ret, (bb[1] - bb[0]) * (bb[3] - bb[2]))

print(ret / 4.0)
### BUGGY CODE ###

import collections
n = int(input())

s = []
C = []
for i in range(n):                                                                                                                                                                                          
    s.append(input())                                                                                                                                                                                       
    c = collections.Counter(s[i])                                                                                                                                                                           
    C.append(c)                                                                                                                                                                                             

count = 0
for j in range(n-1):                                                                                                                                                                                        
    for k in range(j+1, n):                                                                                                                                                                                   
        if C[j].items() == C[k].items():                                                                                                                                                                    
            count += 1                                                                                                                                                                                      

print(count)

### FIXED CODE ###

N = int(input())
ana = {}
answer = 0

for i in range(N):
    s = sorted(input())
    new_str = ''.join(s)
    flag = 0

    if new_str in ana.keys():
        ana[new_str] += 1
        answer += ana[new_str]
        flag = 1

    if flag == 0:
        ana[new_str] = 0

print(answer)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        gamed = [0 for _ in range(N)]
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                continue
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

mod = 10 ** 9 + 7
N = 100000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

d = {}
n1 = 0
n2 = 0
n3 = 0

for i, ai in enumerate(a):
    if ai not in d:
        d[ai] = i
    else:
        n1 = d[ai]
        n2 = i - d[ai] - 1
        n3 = n - i - 1
        break

for i in range(1, n+2):
    ans = 0
    # Xを選ばない
    ans += cmb(n-1, i) # 0
    # Xを2回選ぶ
    ans += cmb(n-1, i-2) # 2
    # Xを1回選ぶ
    ans += cmb(n-1-n2, i-1) # 
    for j in range(1, n2+1):
        ans += 2 * cmb(n2, j) * cmb(n-n2-1, i-j-1) % mod
        ans %= mod
    print(ans % mod)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

mod = 10 ** 9 + 7
N = 100000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

d = {}

# n1個 X n2個 X n3個
n1 = 0
n2 = 0
n3 = 0

for i, ai in enumerate(a):
    if ai not in d:
        d[ai] = i
    else:
        n1 = d[ai]
        n2 = i - d[ai] - 1
        n3 = n - i
        break

for i in range(1, n+2):
    ans = 0
    # Xを選ばない
    ans += cmb(n-1, i)
    # Xを2回選ぶ
    ans += cmb(n-1, i-2)
    # Xを1回選ぶ かつ Xの間からは選ばない
    ans += cmb(n-1-n2, i-1)
    # Xを1回選ぶ かつ Xの間から一つ以上選ぶ
    if i >= 2 and i <= n:
        ans += 2 * (cmb(n2+n1+n3, i-1) - cmb(n1+n3, i-1))

    print(ans % mod)
### BUGGY CODE ###

import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r:, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

RcntL = np.cumsum(RcntL, axis=1)

for p, q in pq:
    ans = RcntL[q, q] - RcntL[q, p - 1]
    print(ans)


### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

RcntL = np.cumsum(RcntL, axis=0)
RcntL = np.cumsum(RcntL, axis=1)

for p, q in pq:
    ans = RcntL[q, q] - RcntL[q, p - 1]
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = ''

for i in range(1,n+1):
  if ans != '':
    ans = ans + ' '
  ans = ans + str(a.index(i)+1)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = {}
ans = ''

for i in range(0,n):
  d[a[i]] = i+1

d_sorted = sorted(d.items(), key=lambda x:x[0])

for i in range(n):
  if ans != '':
    ans = ans + ' '
  ans = ans + str(d_sorted[i][1])

print(ans)
### BUGGY CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

"""
S = "s0 s1 ... s(N-1)"に対して"sl s(l+1) ... s(r-1)"が素数Pで割り切れるかを考える。
これはa_i := int("si s(i+1) ... s(N-1)")と定めることで、
    (a_l - a_r) / 10^{N-r} ¥cong 0  (mod P)
と定式化できる。

（整数関連の区間の問題は後ろからの累積和が相性良さそう。頭からの累積を考えたのが敗因な気がする）

Pが2でも5でもない場合は、上式は
    a_l - a_r ¥cong 0 (mod P)
に同値であるから、各a_iのmod Pでの値を辞書にまとめておけば良さそう。
Pが2, 5のいずれかの場合は偶然チェックが簡単なので解ける。
"""

ans = 0
if P == 2:
    for i in range(N):
        a = int(S[i])
        if a % 2 == 0:
            ans += i + 1
elif P == 5:
    for i in range(N):
        a = int(S[i])
        if a == 0 or a == 5:
            ans += i + 1
else:
    S += "0" # 上の定式化の都合上、r = Nのケースが必要なので
    d = defaultdict(int)
    for i in range(N + 1):
        a = int(S[i:]) % P
        d[a] += 1

    for res in d:
        ans += d[res] * (d[res] - 1) // 2

print(ans)    


### FIXED CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

"""
S = "s0 s1 ... s(N-1)"に対して"sl s(l+1) ... s(r-1)"が素数Pで割り切れるかを考える。
これはa_i := int("si s(i+1) ... s(N-1)")と定めることで、
    (a_l - a_r) / 10^{N-r} ¥cong 0  (mod P)
と定式化できる。

（整数関連の区間の問題は後ろからの累積和が相性良さそう。頭からの累積を考えたのが敗因な気がする）

Pが2でも5でもない場合は、上式は
    a_l - a_r ¥cong 0 (mod P)
に同値であるから、各a_iのmod Pでの値を辞書にまとめておけば良さそう。
Pが2, 5のいずれかの場合は偶然チェックが簡単なので解ける。
"""

ans = 0
if P == 2:
    for i in range(N):
        a = int(S[i])
        if a % 2 == 0:
            ans += i + 1
elif P == 5:
    for i in range(N):
        a = int(S[i])
        if a == 0 or a == 5:
            ans += i + 1
else:
    S += "0" # 上の定式化の都合上、r = Nのケースが必要なので
    d = defaultdict(int)
    r = 0
    d[0] += 1
    for i in range(N - 1, -1, -1):
        """
        ここでS[i:]を毎回Pで割るとTLEする（桁の大きい演算はやはり負担が大きいのか？）
        (a_i % P)をi = N, N-1,...の降順に求めていくことを考えれば、
        前の計算結果が使える、特に繰り返し二乗法が使えるのでだいぶ早くなるみたい。
        """
        r += int(S[i]) * pow(10, N - i - 1, P)
        r %= P
        d[r] += 1

    for num in d.values():
        ans += num * (num - 1) // 2

print(ans)
### BUGGY CODE ###

L,R=(int(x) for x in input().split())

minimum=10000000000
for i in range(L,R):
    for j in range(i+1,R+1):
        candidate=(i*j)%2019
        if(minimum>candidate):
            minimum=candidate
print(minimum)

### FIXED CODE ###

L,R=(int(x) for x in input().split())
mod_list=[]
minimum=10000000000
index=0
flag=0
for i in range(L,R):
    for j in range(i+1,R+1):
        if((i*j)%2019==0):
            minimum=0
            flag=1
            break
        else:
            candidate=(i*j)%2019
            if(minimum>candidate):
                minimum=candidate
    if(flag==1):
        break
print(minimum)
### BUGGY CODE ###

from bisect import bisect_left
 
N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()
 
sum = 0

for i in range(N):
    for j in range(N):
        if i < j:
            less_than_c = bisect_left(Lmat, Lmat[i]+Lmat[j])
            more_than_b = bisect_left(Lmat, Lmat[j]+1)

            sum += less_than_c - more_than_b 

print(sum)

### FIXED CODE ###

from bisect import bisect_left
 
N = int(input())
Lmat = [int(n) for n in input().split()]
Lmat.sort()
 
sum = 0

for i in range(N):
    for j in range(i + 1, N):
        sum += bisect_left(Lmat, Lmat[i]+Lmat[j]) - (j + 1)
        
print(sum)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(N)]
INF = 10**5
n = 10*N + 1
dp = [[[INF]*n for i in range(n)] for j in range(N+1)]
dp[0][0][0] = 0

for i, (a, b, c) in enumerate(abc, 1):
  for j in range(n):
    for k in range(n):
      dp[i][j][k] = dp[i-1][j][k]
      if a <= j and b <= k:
        dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-a][k-b]+c)

ans = INF
dp[-1][0][0] = INF
for j in range(n):
  for k in range(n):
    if j * Mb == k*Ma:
      ans = min(ans, dp[-1][j][k])

if ans < INF:
  print(ans)
else:
  print(-1)

### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
abc = [list(map(int, input().split())) for i in range(N)]
INF = 10**5
n = 10*N + 1
dp = [[[INF]*n for i in range(n)] for j in range(N+1)]
dp[0][0][0] = 0

for i, (a, b, c) in enumerate(abc, 1):
  for j in range(n):
    for k in range(n):
      dp[i][j][k] = dp[i-1][j][k]
      if a <= j and b <= k:
        dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-a][k-b]+c)

ans = INF
dp[-1][0][0] = INF
for j in range(n):
  for k in range(n):
    if j * Mb == k*Ma:
      ans = min(ans, dp[-1][j][k])

if ans < INF:
  print(ans)
else:
  print(-1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
k = inp()
n = len(s)
t = []
for i in s:
    t.append(ord(i) - ord('a'))
se = set()
for i in range(26):
    for j in range(n):
        if t[j] == i:
            for l in range(j,n):
                tmp = s[j:l+1]
                if tmp == '':
                    continue
                se.add(tmp)
    if len(se) >= k:
        break
res = sorted(list(se))
print(res[k-1])

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
k = inp()
n = len(s)
t = []
for i in s:
    t.append(ord(i) - ord('a'))
se = set()
for i in range(26):
    for j in range(n):
        if t[j] == i:
            for l in range(j,min(j+k,n)):
                tmp = s[j:l+1]
                if tmp == '':
                    continue
                se.add(tmp)
    if len(se) >= k:
        break
res = sorted(list(se))
print(res[k-1])
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def ins(ls, i):
  ls[i] = True

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    [ins(L, i) for i in blacks]
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
magic = [_ for _ in range(N)]

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []

def solve(start, power, point, maryoku):
  if start >= H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print(min(anskouho))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

H, N = map(int, input().split())
magic = [_ for _ in range(N)]

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = [float('inf')]

def solve(start, power, point, maryoku):
  if start == H:
    print(min(point, min(anskouho)))
    exit()
  elif start > H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)

for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])

print(min(anskouho))
### BUGGY CODE ###

K,S=map(int,input().split())
N=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                N+=1
print(N)  

### FIXED CODE ###

K,S=map(int,input().split())
N=0
for i in range(K+1):
    for j in range(K+1):
        if i+j<=S and i+j+K>=S:
            N+=1
print(N)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))



f=[True]*(max(A)+1)
chk=[0]*(max(A)+1)

for a in A:
    chk[a]+=1

for a in A:
    cnt=2
    while a*cnt<=max(A):
        f[a*cnt]=False
        cnt+=1
ans=0
for a in A:
    if f[a]==True and chk[a]==1:
        ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))

mx=max(A)
f=[True]*(mx+1)
chk=[0]*(mx+1)

for a in A:
    chk[a]+=1

for a in A:
    cnt=2
    while a*cnt<=mx:
        f[a*cnt]=False
        cnt+=1
ans=0
for a in A:
    if f[a]==True and chk[a]<=1:
        ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
cnt = []
for j in range(1,N+1):
        cnt.append(A.count(j))
for ko in cnt:
    print(ko)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
cnt = [0]*N

for a in A:
    cnt[a-1] += 1
print('\n'.join(map(str,cnt)))
#count()ではTLE
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    count2 = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        tmp = count
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count == tmp : count2 += 1
        if count2 > 100 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.97
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N, K = map(int, input().split())
ashi = list(map(int, input().split()))

if N<=K:    
    print(abs(ashi[-1]-ashi[0]))
    exit()

arr = [0]*N
for i in range(1,K+1,1):
    arr[i] = abs(ashi[i]-ashi[0])


for i in range(K+1,N,1):
    x = arr[i-1]+abs(ashi[i]-ashi[i-1])
    for j in range(1,K+1,1):
        if arr[i-j]+abs(ashi[i]-ashi[i-j]) < x:
            x=arr[i-j]+abs(ashi[i]-ashi[i-j])
    arr[i] = x

print(arr[-1])

### FIXED CODE ###

N, K = map(int, input().split())
ashi = list(map(int, input().split()))
 
if N<=K:    
    print(abs(ashi[-1]-ashi[0]))
    exit()
 
arr = [0]*N
for i in range(1,K+1,1):
    arr[i] = abs(ashi[i]-ashi[0])
 
 
for i in range(K+1,N,1):
    x = arr[i-1]+abs(ashi[i]-ashi[i-1])
    for j in range(1,K+1,1):
        if arr[i-j]+abs(ashi[i]-ashi[i-j]) < x:
            x=arr[i-j]+abs(ashi[i]-ashi[i-j])
    arr[i] = x
 
print(arr[-1])
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,reverse=True,key=lambda x: x[1])
D = []
i = 0

for B,C in BC:
    for b in range(B):
        D.append(C)

for a,d in zip(A,D):
    if a < d:
        A[i] = D[i]
    i += 1

print(sum(A))

### FIXED CODE ###

import sys

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

def main():

    N,M = map(int,input().split())
    A = sorted(list(map(int,input().split())))
    BC = [list(map(int,input().split())) for _ in range(M)]
    BC = sorted(BC,reverse=True,key=lambda x: x[1])
    D = []

    for B,C in BC:
        for b in range(B):
            if len(D) != N:
                D.append(C)
            else:
                break
        else:
            continue
        break

    for i in range(len(D)):
        if A[i] < D[i]:
            A[i] = D[i]
        else:
            break

    print(sum(A))

if __name__ == "__main__":
    main()