TnT/CodeNet4Repair huggingface dataset:
Problem:
On a two-dimensional plane, there are N red points and N blue points. The coordinates of the i-th red point are (a_i, b_i), and the coordinates of the i-th blue point are (c_i, d_i).  A red point and a blue point can form a _friendly pair_ when, the x-coordinate of the red point is smaller than that of the blue point, and the y-coordinate of the red point is also smaller than that of the blue point.  At most how many friendly pairs can you form? Note that a point cannot belong to multiple pairs.

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

from bisect import bisect_right
N = int(input())
ab = [list(mapint()) for _ in range(N)]
cd = [list(mapint()) for _ in range(N)]
ab.sort()
cd.sort(key=lambda x: x[1])
clis = [c for c, d in cd]
checked = [0]*N

cdidx = 0
ans = 0
for n in range(N):
    a, b = ab[n]
    cdidx = bisect_right(clis, a)
    if cdidx>=N:
        break
    for i in range(cdidx, N):
        if checked[i]:
            continue
        c, d = cd[i]
        if a<c and b<d:
            ans += 1
            checked[i] = 1
            break

print(ans)

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

from bisect import bisect_right
N = int(input())
ab = [list(mapint()) for _ in range(N)]
cd = [list(mapint()) for _ in range(N)]
ab.sort(reverse=True)
cd.sort(key=lambda x: x[1])
checked = [0]*N

ans = 0
for n in range(N):
    a, b = ab[n]
    for i in range(N):
        if checked[i]:
            continue
        c, d = cd[i]
        if a<c and b<d:
            ans += 1
            checked[i] = 1
            break

print(ans)
Problem:
明日から、待ちに待った夏休みが始まります。なのでわたしは、友だちを誘って、海に遊びに行くこ とに決めました。  けれども、わたしの友だちには、恥ずかしがりやさんが多いです。その人たちは、あまり多くの人が いっしょに来ると知ったら、きっと嫌がるでしょう。  ほかにも、わたしの友だちには、目立ちたがりやさんも多いです。その人たちは、いっしょに来る人 があまり多くないと知れば、きっと嫌がるでしょう。  それと、わたしの友だちには、いつもは目立ちたがりやなのに実は恥ずかしがりやさんな人もいま す。その人たちは、いっしょに来る人が多すぎても少なすぎても、きっと嫌がるでしょう。  こういうのは、大勢で行った方が楽しいはずです。だからわたしは、できるだけたくさんの友だちを 誘いたいと思っています。けれども、嫌がる友だちを無理やり連れていくのはよくありません。  いったい、わたしは最大で何人の友だちを誘うことができるのでしょうか。  わたしは、こういう頭を使いそうな問題が大の苦手です。なので、あなたにお願いがあります。もし よろしければ、わたしの代わりにこの問題を解いていただけないでしょうか。いえ、決して無理にと は言いません。けれど、もし解いていただるのでしたら、わたしはとても嬉しいです。

Incorrect submission (verdict: Wrong Answer):
N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]

diff = [0] * 100001
for k in l :
    diff[k[0] - 1] += 1
    diff[k[1]] -= 1

hist = [0,0]
for i in range(2, N + 1) :
    hist.append(hist[-1] + diff[i-1])

print(max([y for (x,y) in zip(hist, range(N + 1)) if x + 1 >= y]))

Fixed, accepted submission:
N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]

diff = [0] * 100002
for k in l :
    diff[k[0] - 1] += 1
    diff[k[1]] -= 1

hist = [0,0]
for i in range(2, N + 2) :
    hist.append(hist[-1] + diff[i-1])

print(max([0] + [y - 1 for (x,y) in zip(hist, range(N + 2)) if x + 1 >= y]))
Problem:
There is a triangle formed by three points $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ on a plain.  Write a program which prints "YES" if a point $P$ $(x_p, y_p)$ is in the triangle and "NO" if not.

Incorrect submission (verdict: Wrong Answer):
import sys

def crossMulti(p1, p2):
    return p1[0] * p2[1] - p1[1] * p2[0]
           
lines = sys.stdin.readlines()
for line in lines:
    Zd = []
    x1, y1, x2, y2, x3, y3, xp, yp = map(float, line.split())
    Ps = [(x2-x1, y2-y1),(x3-x2, y3-y2),(x1-x3, y1-y3)]
    Px = [(xp-x1, yp-y1),(xp-x2, yp-y2),(xp-x3, yp-y3)]
    for p in range(3):
        Zd.append(crossMulti(Ps[p], Px[p]))
    Zd = [x > 0 for x in Zd]

    if (Zd[0] and Zd[1] and Zd[2]) or not(Zd[0] or Zd[1] or Zd[2]):
        print('Yes')
    else:
        print('No')
    

Fixed, accepted submission:
import sys

def crossMulti(p1, p2):
    return p1[0] * p2[1] - p1[1] * p2[0]
           
lines = sys.stdin.readlines()
for line in lines:
    Zd = []
    x1, y1, x2, y2, x3, y3, xp, yp = map(float, line.split())
    Ps = [(x2-x1, y2-y1),(x3-x2, y3-y2),(x1-x3, y1-y3)]
    Px = [(xp-x1, yp-y1),(xp-x2, yp-y2),(xp-x3, yp-y3)]
    for p in range(3):
        Zd.append(crossMulti(Ps[p], Px[p]))
    Zd = [x > 0 for x in Zd]

    if (Zd[0] and Zd[1] and Zd[2]) or not(Zd[0] or Zd[1] or Zd[2]):
        print('YES')
    else:
        print('NO')
Problem:
You are given four digits N_1, N_2, N_3 and N_4. Determine if these can be arranged into the sequence of digits "1974".

Incorrect submission (verdict: Wrong Answer):

n=list(map(int,input().split()))
if ('1' in n) and ('9' in n) and ('7' in n) and ('4' in n):
    print('YES')
else:
    print('NO')

Fixed, accepted submission:

n=list(map(int,input().split()))
if (1 in n) and (9 in n) and (7 in n) and (4 in n):
    print('YES')
else:
    print('NO')
Problem:
Sitting in a station waiting room, Joisino is gazing at her train ticket.  The ticket is numbered with four digits A, B, C and D in this order, each between 0 and 9 (inclusive).  In the formula A op1 B op2 C op3 D = 7, replace each of the symbols op1, op2 and op3 with `+` or `-` so that the formula holds.  The given input guarantees that there is a solution. If there are multiple solutions, any of them will be accepted.

Incorrect submission (verdict: Wrong Answer):
from itertools import *

ABCD = input()

n = len(ABCD) - 1 

plumi_list = list(product(["+", "-"], repeat=n))

print(plumi_list)

for bit in range(1 << n):
    formula = ABCD[0]
    for num, op in zip(ABCD[1:], plumi_list[bit]):
        formula += op + num
        ans = eval(formula)
        if ans == 7:
            print(formula + "=7")
            break
    else:
        continue
    break



Fixed, accepted submission:
from itertools import *

ABCD = input()

n = len(ABCD) - 1 

plumi_list = list(product(["+", "-"], repeat=n))

for bit in range(1 << n):
    formula = ABCD[0]
    for num, op in zip(ABCD[1:], plumi_list[bit]):
        formula += op + num
        ans = eval(formula)

    if ans == 7:
        print(formula + "=7")
        break
Problem:
We will buy a product for N yen (the currency of Japan) at a shop.  If we use only 1000-yen bills to pay the price, how much change will we receive?  Assume we use the minimum number of bills required.

Incorrect submission (verdict: Wrong Answer):
n = int(input())
print(n % 1000)

Fixed, accepted submission:
n = int(input())
i = 0
m = n
while (m > 0):
    m = m - 1000
    i = i + 1

print(i*1000 - n)
Problem:
Iroha loves _Haiku_. Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.  To create a Haiku, Iroha has come up with three different phrases. These phrases have A, B and C syllables, respectively. Determine whether she can construct a Haiku by using each of the phrases once, in some order.

Incorrect submission (verdict: Wrong Answer):


import sys

# import itertools

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().decode('utf8').rstrip().split()

print('Yes' if S.count('5') == 2 and S.count('7') == 1 else 'No')


Fixed, accepted submission:


import sys

# import itertools

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = readline().decode('utf8').rstrip().split()

print('YES' if S.count('5') == 2 and S.count('7') == 1 else 'NO')
Problem:
Let w be a string consisting of lowercase letters. We will call w _beautiful_ if the following condition is satisfied:    * Each lowercase letter of the English alphabet occurs even number of times in w.  You are given the string w. Determine if w is beautiful.

Incorrect submission (verdict: Wrong Answer):
s = input()

def isBeautiful(s):
  dict = {}
  for i in s:
    if i not in dict:
      dict[i] = 1
    else:
      dict[i] += 1
      
  for key in dict:
    if dict[key] % 2 != 0:
      return False
    
  return True
  
print(isBeautiful(s))

Fixed, accepted submission:
s = input()

def isBeautiful(s):
  dict = {}
  for i in s:
    if i not in dict:
      dict[i] = 1
    else:
      dict[i] += 1
      
  for key in dict:
    if dict[key] % 2 != 0:
      return "No"
    
  return "Yes"
  
print(isBeautiful(s))
Problem:
Print all the integers that satisfies the following in ascending order:    * Among the integers between A and B (inclusive), it is either within the K smallest integers or within the K largest integers.

Incorrect submission (verdict: Wrong Answer):
# coding: utf-8
# Your code here!

A,B,K = list(map(int,input().split(" ")))
ans = []
for i in range(K):
    if A<=A+i<=B:
        ans.append(A+i)
    if A<=A-i<=B:
        ans.append(B-i)
ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)
        

Fixed, accepted submission:
# coding: utf-8
# Your code here!

A,B,K = list(map(int,input().split(" ")))
ans = []
for i in range(K):
    if A<=A+i<=B:
        ans.append(A+i)
    if A<=B-i<=B:
        ans.append(B-i)
ans = list(set(ans))
ans.sort()
for i in ans:
    print(i)
Problem:
Snuke has N sticks. The length of the i-th stick is l_i.  Snuke is making a snake toy by joining K of the sticks together.  The length of the toy is represented by the sum of the individual sticks that compose it. Find the maximum possible length of the toy.

Incorrect submission (verdict: Wrong Answer):
N,K=map(int,input().split())
l=list(map(int,input().split()))

l.sort(reverse=True)

print(sum(l[0:K+1]))

Fixed, accepted submission:
N,K=map(int,input().split())
l=list(map(int,input().split()))

l.sort(reverse=True)

print(sum(l[0:K]))
Problem:
Takahashi bought a piece of apple pie at ABC Confiserie. According to his memory, he paid N yen (the currency of Japan) for it.  The consumption tax rate for foods in this shop is 8 percent. That is, to buy an apple pie priced at X yen before tax, you have to pay X \times 1.08 yen (rounded down to the nearest integer).  Takahashi forgot the price of his apple pie before tax, X, and wants to know it again. Write a program that takes N as input and finds X. We assume X is an integer.  If there are multiple possible values for X, find any one of them. Also, Takahashi's memory of N, the amount he paid, may be incorrect. If no value could be X, report that fact.

Incorrect submission (verdict: Wrong Answer):
n=int(input())
ans=0
for i in range(1,50000+1):
    z=i*1.08
    if n<=z<(n+1):
        ans=z
        break
if ans==0:
    print(":(")
else:
    print(ans)



Fixed, accepted submission:
n=int(input())
ans=0
for i in range(1,50000+1):
    z=i*1.08
    if n<=z<(n+1):
        ans=i
        break
if ans==0:
    print(":(")
else:
    print(ans)
Problem:
E869120 found a chest which is likely to contain treasure.   However, the chest is locked. In order to open it, he needs to enter a string S consisting of lowercase English letters.   He also found a string S', which turns out to be the string S with some of its letters (possibly all or none) replaced with `?`.  One more thing he found is a sheet of paper with the following facts written on it:    * Condition 1: The string S contains a string T as a contiguous substring.   * Condition 2: S is the lexicographically smallest string among the ones that satisfy Condition 1.  Print the string S.   If such a string does not exist, print `UNRESTORABLE`.

Incorrect submission (verdict: Wrong Answer):
S = str(input())
T = str(input())
ans = []

flag = False
T_l = len(T)
S_l = len(S)
u = 0

while u < S_l:
    cnt = 0
    name = S[u]

    if name == T[0] or name == "?":
        cnt += 1
        u += 1
        for j in range(u,S_l):
            if cnt == T_l:
                break
            if S[j] == "?" or S[j] == T[cnt]:
                cnt += 1
                u += 1
            else:
                break
        
        if cnt == T_l:
            ans = ans + list(T)
            flag = True
        else:
            for j in range(cnt):
                if S[j] == "?":
                    ans.append("a")
                else:
                    ans.append(S[j])

    else:
        ans.append(name)
        u += 1
        continue

if flag:
    ans = "".join(ans)
    print(*ans)
else:
    print("UNRESTORABLE")

Fixed, accepted submission:
sd = input()
t = input()

n = len(sd)
m = len(t)
s = []

for i in range(n - m, -1, -1):
    t_kamo = sd[i:i + m]
    for j in range(m + 1):
        if j == m:
            print((sd[:i] + t + sd[i + len(t):]).replace("?", "a"))
            exit()
        if t_kamo[j] == "?":
            continue
        elif t_kamo[j] != t[j]:
            break

print("UNRESTORABLE")
Problem:
You have A 500-yen coins, B 100-yen coins and C 50-yen coins (yen is the currency of Japan). In how many ways can we select some of these coins so that they are X yen in total?  Coins of the same kind cannot be distinguished. Two ways to select coins are distinguished when, for some kind of coin, the numbers of that coin are different.

Incorrect submission (verdict: Wrong Answer):
A,B,C,X = map(int,open(0).read().split())
a = 0
for i in range(1,A+1):
    for l in range(1,B+1):
        for q in range(1,C+1):
            if 500*i+100*B+50*C == X:
                a += 1
print(a)

Fixed, accepted submission:
A,B,C,X = map(int,open(0).read().split())
a = 0
for i in range(A+1):
    for l in range(B+1):
        for q in range(C+1):
            if 500*i+100*l+50*q == X:
                a += 1
print(a)
Problem:
Iroha has a sequence of N strings S_1, S_2, ..., S_N. The length of each string is L.  She will concatenate all of the strings in some order, to produce a long string.  Among all strings that she can produce in this way, find the lexicographically smallest one.  Here, a string s=s_1s_2s_3...s_n is _lexicographically smaller_ than another string t=t_1t_2t_3...t_m if and only if one of the following holds:    * There exists an index i(1≦i≦min(n,m)), such that s_j = t_j for all indices j(1≦j<i), and s_i<t_i.   * s_i = t_i for all integers i(1≦i≦min(n,m)), and n<m.

Incorrect submission (verdict: Wrong Answer):
a = input().split()

s = [input() for i in range(int(a[0]))]
b = ''

s.sort()
print(s)

for i in range(int(a[0]),0):
  b = s[i] + b
  
print(b)

Fixed, accepted submission:
a = input().split()

s = [input() for i in range(int(a[0]))]
b = ''

s.sort()

b = ''.join(s)

print(b)
Problem:
Takahashi is a user of a site that hosts programming contests.   When a user competes in a contest, the _rating_ of the user (not necessarily an integer) changes according to the _performance_ of the user, as follows:    * Let the current rating of the user be a.   * Suppose that the performance of the user in the contest is b.   * Then, the new rating of the user will be the avarage of a and b.  For example, if a user with rating 1 competes in a contest and gives performance 1000, his/her new rating will be 500.5, the average of 1 and 1000.  Takahashi's current rating is R, and he wants his rating to be exactly G after the next contest.   Find the performance required to achieve it.

Incorrect submission (verdict: Wrong Answer):
R = float(input())
G = float(input())
print(G * 2 - R)


Fixed, accepted submission:
R = int(input())
G = int(input())
print(G * 2 - R)
Problem:
We ask you to select some number of positive integers, and calculate the sum of them.  It is allowed to select as many integers as you like, and as large integers as you wish. You have to follow these, however: each selected integer needs to be a multiple of A, and you need to select at least one integer.  Your objective is to make the sum congruent to C modulo B. Determine whether this is possible.  If the objective is achievable, print `YES`. Otherwise, print `NO`.

Incorrect submission (verdict: Wrong Answer):
A,B,C=map(int,input().split())
mod=set()
tmp=0
D=A
while tmp not in mod:
    mod.add(tmp)
    tmp=D%B
    if tmp==C:
        print('Yes')
        exit()
    D+=A
print('No')

Fixed, accepted submission:
A,B,C=map(int,input().split())
mod=set()
tmp=0
D=A
while tmp not in mod:
    mod.add(tmp)
    tmp=D%B
    if tmp==C:
        print('YES')
        exit()
    D+=A
print('NO')
Problem:
You are given an integer N. Find the number of the positive divisors of N!, modulo 10^9+7.

Incorrect submission (verdict: Wrong Answer):
import math

N = int(input())
mod = 10**9+7

def get_primes(n):
    ps = [0, 0] + [i for i in range(2, n)]
    for i in range(2, n):
        if ps[i] == 0:
            continue
        for j in range(i * i, n, i):
            ps[j] = 0
    return [p for p in ps if p]


prime = get_primes(N)

ans = 1
for p in prime:
    tmp = 0
    for i in range(1, int(math.log(N, p))+1):
        tmp += N // (p**i)

    ans = (ans * (tmp + 1)) % mod

print(ans)





Fixed, accepted submission:
import math

N = int(input())
mod = 10**9+7

def get_primes(n):
    ps = [0, 0] + [i for i in range(2, n+1)]
    for i in range(2, n+1):
        if ps[i] == 0:
            continue
        for j in range(i * i, n+1, i):
            ps[j] = 0
    return [p for p in ps if p]


prime = get_primes(N)

ans = 1
for p in prime:
    tmp = 0
    for i in range(1, int(math.log(N, p))+1):
        tmp += N // (p**i)

    ans = (ans * (tmp + 1)) % mod

print(ans)
Problem:
Snuke has one biscuit and zero Japanese yen (the currency) in his pocket. He will perform the following operations exactly K times in total, in the order he likes:    * Hit his pocket, which magically increases the number of biscuits by one.   * Exchange A biscuits to 1 yen.   * Exchange 1 yen to B biscuits.  Find the maximum possible number of biscuits in Snuke's pocket after K operations.

Incorrect submission (verdict: Wrong Answer):
K,A,B=map(int,input().split())
c=K-A;d=B-A
print(K+1 if d<2 or c<1 else A+c%2+c//2*d)

Fixed, accepted submission:
K,A,B=map(int,input().split())
c=K-A+1;d=B-A
print(K+1 if d<2 or c<1 else A+c%2+c//2*d)
Problem:
AtCoDeer the deer found two positive integers, a and b. Determine whether the product of a and b is even or odd.

Incorrect submission (verdict: Wrong Answer):
a,b=map(int,input().split())
if (a*b)&1:print("Even")
else:print("Odd")

Fixed, accepted submission:
a,b=map(int,input().split())
if ((a*b)&1)==0:print("Even")
else:print("Odd")
Problem:
Write a program which reads three integers a, b and c, and prints "Yes" if a < b < c, otherwise "No".

Incorrect submission (verdict: Wrong Answer):
a, b, c = map(int, input().split())
print('YES' if a < b < c else 'NO')

Fixed, accepted submission:
a, b, c = map(int, input().split())
print('Yes' if a < b < c else 'No')
Problem:
In this problem, we use the 24-hour clock.  Takahashi gets up exactly at the time H_1 : M_1 and goes to bed exactly at the time H_2 : M_2. (See Sample Inputs below for clarity.) He has decided to study for K consecutive minutes while he is up. What is the length of the period in which he can start studying?

Incorrect submission (verdict: Wrong Answer):
h1,m1,h2,m2,k=map(int,input().split())
t=h2*60+m2-(h1*60+m1)
t-=0.5
g=t//k
print(g*k)

Fixed, accepted submission:
h1,m1,h2,m2,k=map(int,input().split())
t=h2*60+m2-(h1*60+m1)
print(max(0,t-k))
Problem:
Write a program of the Bubble Sort algorithm which sorts a sequence _A_ in ascending order. The algorithm should be based on the following pseudocode:                 BubbleSort(A) 1 for i = 0 to A.length-1 2     for j = A.length-1 downto i+1 3         if A[j] < A[j-1] 4             swap A[j] and A[j-1]   Note that, indices for array elements are based on 0-origin.  Your program should also print the number of swap operations defined in line 4 of the pseudocode.

Incorrect submission (verdict: Wrong Answer):
if __name__ == '__main__':
    N = input('Please input the number of elements: ')
    N = int(N)
    array = list(map(int,  input('Please input the array: ').split()))
    for i in range(N):
        print(' '.join(map(str, array)))
        for j in range(N-1, i, -1):
            if array[j] < array[j-1]:
                array[j], array[j-1] = array[j-1], array[j]
    print(' '.join(map(str, array)))



Fixed, accepted submission:
def bubble_sort(A):
    global N
    flag = True
    i = 0 
    cnt = 0
    while flag:
        flag = False
        for j in range(N-1, i, -1):
            if A[j] < A[j-1]:
                A[j],A[j-1] = A[j-1],A[j]
                cnt += 1
                flag = True
        i += 1
    return cnt

N = int(input())
A = list(map(int, input().split()))
cnt = bubble_sort(A)
print(' '.join(list(map(str, A))))
print(cnt)
Problem:
You have N items and a bag of strength W. The i-th item has a weight of w_i and a value of v_i.  You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.  Your objective is to maximize the total value of the selected items.

Incorrect submission (verdict: Wrong Answer):
def func(n, W, w):
    
    
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    for i in range(1, len(dp)):
        for j in range(len(dp[0])):
            if j-w[-i][0] >= 0:
                dp[i][j] = max(dp[i-1][j-w[-i][0]] + w[-i][1], dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    
        # print(dp[i])
    return dp[n][W]
n, W = [int(i) for i in input().split()]
w = [[0, 0] for _ in range(n)]
for i in range(n):
    w[i] = [int(i) for i in input().split()]
"""
# print("print(\" vs \" + str(func({}, {}, {})))".format(n, W, w))
print("11 vs " + str(func(4, 6, [[2, 1], [3, 4], [4, 10], [3, 4]])))
print("13 vs " + str(func(4, 6, [[2, 1], [3, 7], [4, 10], [3, 6]])))
print("400 vs " + str(func(4, 10, [[1, 100], [1, 100], [1, 100], [1, 100]])))
print("0 vs " + str(func(4, 1, [[10, 100], [10, 100], [10, 100], [10, 100]])))
"""


Fixed, accepted submission:
def func(n, W, w):  
    _max = 0
    weights = [[] for _ in range(4)]
    for i in range(n):
        weights[w[i][0]-w[0][0]].append(w[i][1])
    for i in range(len(weights)):
        weights[i].sort()
        weights[i].append(0)
        weights[i].reverse()
        for j in range(1, len(weights[i])):
            weights[i][j] += weights[i][j-1]
    # print(weights)
    for i in range(len(weights[0])):
        # print("i:{}".format(i))
        for j in range(len(weights[1])):
            
            for k in range(len(weights[2])):
                for l in range(len(weights[3])):
                    
                    if w[0][0]*i\
                            + (w[0][0]+1)*j\
                            + (w[0][0]+2)*k\
                            + (w[0][0]+3)*l <= W:
                        
                        # j]+weights[2][k]+weights[3][l]))
                        _max = max(_max, weights[0][i]+weights[1][j]+weights[2][k]+weights[3][l])
    return _max


n, W = [int(i) for i in input().split()]
w = [[0, 0] for _ in range(n)]
for i in range(n):
    w[i] = [int(i) for i in input().split()]
print(func(n, W, w))
"""
# print("print(\" vs \" + str(func({}, {}, {})))".format(n, W, w))
print("11 vs " + str(func(4, 6, [[2, 1], [3, 4], [4, 10], [3, 4]])))
print("13 vs " + str(func(4, 6, [[2, 1], [3, 7], [4, 10], [3, 6]])))
print("400 vs " + str(func(4, 10, [[1, 100], [1, 100], [1, 100], [1, 100]])))
print("0 vs " + str(func(4, 1, [[10, 100], [10, 100], [10, 100], [10, 100]])))
"""