#import <Foundation/Foundation.h>
#import <stdlib.h>
#import <stdarg.h>
#import <string.h>
typedef NSInteger Int;
typedef unsigned long long UINT;
#ifndef _OS_OSTYPES_H
typedef NSUInteger UInt;
#endif
/// NSSet literal
#if !defined($)
#define $(...)  ([NSSet setWithArray: @[__VA_ARGS__]])
#endif
@interface NSArray (Extension)
+(instancetype)integerArrayWithRange:(NSRange)range; // NSMakeRange(4,3) -> @[@4,@5,@6]
-(NSMutableArray*)integerArray;
-(NSMutableArray*)stringArray;
-(Int*)integerCArray; // Int をラップした NSNumber* を要素に持つ配列を Int* 型のC言語配列にmallocして変換
-(char**)stringCArrayWithMaxLength:(UInt)maxLength; // NSString* を要素に持つ配列を char** 型のC言語2次元配列にmallocして変換（maxLength: 文字列長の上限）
-(Int)integerAtIndex:(UInt)index;
-(Int)firstInteger;
-(Int)secondInteger;
-(Int)thirdInteger;
-(Int)fourthInteger;
-(double)doubleAtIndex:(UInt)index;
-(NSString*)stringAtIndex:(UInt)index;
-(NSMutableArray*)indexesOfObject:(id)object;
-(NSArray*)subarrayTo:(UInt)index;
-(NSArray*)subarrayFrom:(UInt)index;
-(NSArray*)subarrayFrom:(UInt)start to:(UInt)end;
-(NSArray*)filteredArrayUsingPredicateFormat:(NSString*)format, ...; // [numbers filteredArrayUsingPredicateFormat:@"SELF < %@", @(integer)] のように使ってfilterする
-(NSMutableArray*)rotatedArrayBy:(Int)advance; // advanceだけ巡回した配列を得る。例：advance=+1 のとき [1,2,3,4] -> [2,3,4,1], advance=-1 のとき [1,2,3,4] -> [4,1,2,3]
-(NSMutableArray*)reversedArray; // 逆順化した配列を得る。
-(NSMutableArray*)intersectionArrayWith:(NSArray*)array;
-(NSMutableArray*)sortedStringArrayWithAscending:(BOOL)ascending; // NSString* を要素に持つ配列を辞書式順序でソート
-(NSMutableArray*)sortedArrayWithAscending:(BOOL)ascending; // NSNumber* を要素に持つ配列をソート
-(NSMutableArray*)quickSortedArrayWithAscending:(BOOL)ascending; // Int をラップした NSNumber* を要素に持つ配列をクイックソート
-(NSMutableArray*)quickSortedDictionariesWithValueForKey:(id)key ascending:(BOOL)ascending; // NSDictionary を要素に持つ配列を key の値（Intをラップした NSNumber*）でクイックソート
-(Int)gcd;
// MARK: Key-Value Coding
-(NSMutableArray*)unique;
-(Int)maxInteger;
-(Int)minInteger;
-(Int)sumInteger;
-(double)maxDouble;
-(double)minDouble;
-(double)sumDouble;
-(double)average;
#ifndef _OS_OSTYPES_H
-(id)firstObject;
#endif
-(id)secondObject;
-(id)thirdObject;
-(id)fourthObject;
@end
@interface NSString (Extension)
-(NSMutableArray*)componentsSeparatedByCharacter:(unichar)separator;
-(NSMutableArray*)numbersSeparatedByString:(NSString*)separator;
-(NSMutableArray*)numbersSeparatedByCharacter:(unichar)separator;
-(NSMutableArray*)stringsSeparatedByReturn;
-(NSMutableArray*)numbersSeparatedByReturn;
-(NSMutableArray*)stringsSeparatedBySpace;
-(NSMutableArray*)numbersSeparatedBySpace;
-(NSMutableArray*)splitCharacterEvery:(UInt)number;
-(NSMutableArray*)characterStrings; // 1文字ずつの NSString* の配列を返す
-(NSMutableArray*)characters; // 1文字ずつの unichar をラップした NSNumber の配列を返す
+(NSString*)stringWithCharacterArray:(NSArray*)array; // // 1文字ずつの unichar をラップした NSNumber の配列から文字列を生成
-(unichar)firstCharacter;
-(unichar)lastCharacter;
-(NSString*)leadingSubstringWithLength:(UInt)length;
-(NSString*)trailingSubstringWithLength:(UInt)length;
-(NSComparisonResult)compareInReverseOrder:(NSString*)string;
@end
@interface NSMutableArray (Extension)
+(NSMutableArray*)arrayWithInitialValue:(id)value length:(UInt)length; // 全部が value の値を持つ長さ length のオブジェクトを生成
+(NSMutableArray*)arrayWithNumbers:(Int)count, ...; // 要素数, 数1, 数2, ... から NSMutableArray<NSNumber*> オブジェクトを生成
-(NSMutableArray*)copy;
-(NSMutableArray*)unshift:(id)element;
-(id)shift;
-(NSMutableArray*)push:(id)element;
-(id)pop;
-(void)setInteger:(Int)value atIndex:(UInt)index;
-(NSIndexSet*)moveObjectsFromIndexes:(NSIndexSet*)fromIndexSet toIndex:(NSInteger)insertIndex;
@end
/// MARK: - 定数の定義
#ifndef M_PI
#define M_E         2.71828182845904523536028747135266250   /* e              */
#define M_LOG2E     1.44269504088896340735992468100189214   /* log2(e)        */
#define M_LOG10E    0.434294481903251827651128918916605082  /* log10(e)       */
#define M_LN2       0.693147180559945309417232121458176568  /* loge(2)        */
#define M_LN10      2.30258509299404568401799145468436421   /* loge(10)       */
#define M_PI        3.14159265358979323846264338327950288   /* pi             */
#define M_PI_2      1.57079632679489661923132169163975144   /* pi/2           */
#define M_PI_4      0.785398163397448309615660845819875721  /* pi/4           */
#define M_1_PI      0.318309886183790671537767526745028724  /* 1/pi           */
#define M_2_PI      0.636619772367581343075535053490057448  /* 2/pi           */
#define M_2_SQRTPI  1.12837916709551257389615890312154517   /* 2/sqrt(pi)     */
#define M_SQRT2     1.41421356237309504880168872420969808   /* sqrt(2)        */
#define M_SQRT1_2   0.707106781186547524400844362104849039  /* 1/sqrt(2)      */
#endif
/// MARK: - 整数の演算
Int iminvar(Int len, ...); // 整数可変長のmin。第1引数は比較するものの数。
Int imin2(Int a, Int b);
Int imin3(Int a, Int b, Int c);
Int imaxvar(Int len, ...); // 整数可変長のmax。第1引数は比較するものの数。
Int imax2(Int a, Int b);
Int imas3(Int a, Int b, Int c);
Int isumvar(Int len, ...); // 整数可変長のsum。第1引数は足すものの数。
Int ipow(Int x, Int n); // x^n (xとnは非負整数)
double fpow(double x, Int n); // x^n
Int gcd(Int a, Int b); // GCD
Int gcd2(Int a, Int b); // メモ化GCD
/// MARK: - doubleの演算
double fabs(double x);
double sqrt(double x);
double sin(double x);
double cos(double x);
double tan(double x);
double sinDeg(double x);
double cosDeg(double x);
double tanDeg(double x);
double fceil(double num);
double ffloor(double num);
double fround(double x);
double fln(double x);
double flog(double a, double x);
double flog10(double x);
double flog2(double x);
@implementation NSString (Extension)
-(NSMutableArray*)componentsSeparatedByCharacter:(unichar)separator
{
    return [NSMutableArray arrayWithArray: [self componentsSeparatedByString:[NSString stringWithFormat:@"%C", separator]]];
}
-(NSMutableArray*)numbersSeparatedByString:(NSString*)separator
{
    NSArray *strings = [self componentsSeparatedByString: separator];
    NSMutableArray *numbers = [NSMutableArray array];
    for (NSString *string in strings) {
        if (![string isEqualToString:@""]) {
            [numbers addObject: [NSNumber numberWithInteger: [string integerValue]]];
        }
    }
    return numbers;
}
-(NSMutableArray*)numbersSeparatedByCharacter:(unichar)separator
{
    return [self numbersSeparatedByString:[NSString stringWithFormat:@"%C", separator]];
}
-(NSMutableArray*)stringsSeparatedByReturn
{
    return [self componentsSeparatedByCharacter: '\n'];
}
-(NSMutableArray*)numbersSeparatedByReturn
{
    return [self numbersSeparatedByCharacter: '\n'];
}
-(NSMutableArray*)stringsSeparatedBySpace
{
    return [self componentsSeparatedByCharacter: ' '];
}
-(NSMutableArray*)numbersSeparatedBySpace
{
    return [self numbersSeparatedByCharacter: ' '];
}
-(NSMutableArray*)splitCharacterEvery:(UInt)number
{
    if ([self length] <= number) {
        return [NSMutableArray arrayWithObject: self];
    }
    NSMutableArray  *mArray = [NSMutableArray array];
    NSMutableString *mStr   = [NSMutableString stringWithString: self];
    NSRange range = NSMakeRange(0, number);
    while ([mStr length] > 0) {
        if ([mStr length] < number) {
            [mArray addObject: [NSString stringWithString: mStr]];
            [mStr deleteCharactersInRange:NSMakeRange(0, [mStr length])];
        } else {
            [mArray addObject: [mStr substringWithRange: range]];
            [mStr deleteCharactersInRange: range];
        }
    }
    return mArray;
}
-(NSMutableArray*)characterStrings
{
    return [self splitCharacterEvery: 1];
}
-(NSMutableArray*)characters
{
    NSMutableArray *result = [NSMutableArray array];
    for (UInt i=0; i<[self length]; i++) {
        [result addObject: @([self characterAtIndex: i])];
    }
    return result;
}
+(NSString*)stringWithCharacterArray:(NSArray*)array
{
    NSMutableString *result = [NSMutableString string];
    for (NSNumber *ch in array) {
        [result appendFormat:@"%c", (unsigned int)[ch unsignedIntegerValue]];
    }
    return result;
}
-(unichar)firstCharacter
{
    return [self characterAtIndex: 0];
}
-(unichar)lastCharacter
{
    return ([self length] > 1) ? [self characterAtIndex: [self length] - 1] : '\0';
}
-(NSString*)leadingSubstringWithLength:(UInt)length
{
    if (length <= [self length]) {
        return [self substringWithRange: NSMakeRange(0, length)];
    } else {
        return nil;
    }
}
-(NSString*)trailingSubstringWithLength:(UInt)length
{
    UInt mylength = [self length];
    if (length <= mylength) {
        return [self substringWithRange: NSMakeRange(mylength - length, length)];
    } else {
        return nil;
    }
}
-(NSComparisonResult)compareInReverseOrder:(NSString*)string
{
    NSComparisonResult result = [self compare:string];
    switch (result) {
        case NSOrderedSame:
            return NSOrderedSame;
        case NSOrderedAscending:
            return NSOrderedDescending;
        case NSOrderedDescending:
            return NSOrderedAscending;
    }
}
@end
@implementation NSMutableArray (Extension)
+(NSMutableArray*)arrayWithInitialValue:(id)value length:(UInt)length
{
    NSMutableArray *array = [NSMutableArray array];
    for (UInt i=0; i<length; i++) {
        [array push: value];
    }
    return array;
}
+(NSMutableArray*)arrayWithNumbers:(Int)count, ...
{
    va_list numbers;
    va_start(numbers, count);
    NSMutableArray *array = [NSMutableArray array];
    for (Int i = 0; i < count; i++) {
        [array push: [NSNumber numberWithInt:va_arg(numbers, int)]];
    }
    va_end(numbers);
    return array;
}
-(NSMutableArray*)copy
{
    return [NSMutableArray arrayWithArray: self];
}
-(NSMutableArray*)unshift:(id)element
{
    [self insertObject: element atIndex: 0];
    return self;
}
-(id)shift
{
    if ([self count] > 0) {
        id first = [self objectAtIndex: 0];
        [self removeObjectAtIndex: 0];
        return first;
    } else {
        return nil;
    }
}
-(NSMutableArray*)push:(id)element
{
    [self addObject: element];
    return self;
}
-(id)pop
{
    UInt count = [self count];
    if (count > 0) {
        id last = [self objectAtIndex: count - 1];
        [self removeLastObject];
        return last;
    } else {
        return nil;
    }
}
-(void)setInteger:(Int)value atIndex:(UInt)index
{
    [self replaceObjectAtIndex:index withObject:@(value)];
}
-(NSIndexSet*)moveObjectsFromIndexes:(NSIndexSet*)fromIndexSet toIndex:(NSInteger)insertIndex
{
    NSUInteger adjustedInsertIndex = insertIndex - [fromIndexSet countOfIndexesInRange:(NSRange){0, insertIndex}];
    NSRange destinationRange = NSMakeRange(adjustedInsertIndex, fromIndexSet.count);
    NSIndexSet *destinationIndexes = [NSIndexSet indexSetWithIndexesInRange:destinationRange];
    NSArray *objectsToMove = [self objectsAtIndexes:fromIndexSet];
    [self removeObjectsAtIndexes:fromIndexSet];
    [self insertObjects:objectsToMove atIndexes:destinationIndexes];
    return destinationIndexes;
}
@end
/// MARK: - 整数の演算
Int iminvar(Int len, ...) {
    Int _min, num;
    va_list ap;
    va_start(ap, len);
    _min = va_arg(ap, Int);
    for (Int i = 1; i < len; i++) {
        num = va_arg(ap, Int);
        if (num < _min)
            _min = num;
    }
    va_end(ap);
    return _min;
}
Int imin2(Int a, Int b) {
    return iminvar(2, a, b);
}
Int imin3(Int a, Int b, Int c) {
    return iminvar(3, a, b, c);
}
Int imaxvar(Int len, ...) {
    Int _max, num;
    va_list ap;
    va_start(ap, len);
    _max = va_arg(ap, Int);
    for (Int i = 1; i < len; i++) {
        num = va_arg(ap, Int);
        if (num > _max)
            _max = num;
    }
    va_end(ap);
    return _max;
}
Int imax2(Int a, Int b) {
    return imaxvar(2, a, b);
}
Int imax3(Int a, Int b) {
    return imaxvar(3, a, b);
}
Int isumvar(Int len, ...) {
    va_list ap;
    va_start(ap, len);
    Int sum = 0;
    for (Int i = 0; i < len; i++) {
        sum += va_arg(ap, Int);
    }
    va_end(ap);
    return sum;
}
Int ipow(Int x, Int n) {
    Int result = 1;
    while (n > 0) {
        if ((n % 2) == 0) {
            x *= x;
            n >>= 1;
        } else {
            result *= x;
            n--;
        }
    }
    return result;
}
double fpow(double x, Int n) {
    double result = 1.0;
    while (n > 0) {
        if ((n % 2) == 0) {
            x *= x;
            n >>= 1;
        } else {
            result *= x;
            n--;
        }
    }
    return result;
}
Int gcd(Int a, Int b){
    Int M = MAX(a, b);
    Int m = MIN(a, b);
    if (m == 0) {
        return M;
    }
    Int r = M % m;
    return (r==0) ? m : gcd(r, m);
}
NSMutableDictionary *gcdmap;
Int gcd2(Int a, Int b) {
    if (!gcdmap) {
        gcdmap = [NSMutableDictionary dictionary];
    }
    Int M = MAX(a, b);
    Int m = MIN(a, b);
    if (m == 0) {
        return M;
    }
    NSString *key = [NSString stringWithFormat:@"%ld,%ld", M, m];
    NSNumber *gcd = (NSNumber*)[gcdmap objectForKey:key];
    if (gcd) {
        return [gcd integerValue];
    } else {
        Int r = M % m;
        if (r == 0) {
            [gcdmap setObject:@(m) forKey:key];
            return m;
        } else {
            Int result = gcd2(m, r);
            [gcdmap setObject:@(result) forKey:key];
            return result;
        }
    }
}
/// MARK: - doubleの演算
double fabs(double x) {
    return (x>=0) ? x : -x;
}
double fsqrt(double x) {
    double xHalf = 0.5 * x;
    long tmp = 0x5FE6EB50C7B537AAl - ( *(long*)&x >> 1); //initial guess
    double xRes = * (double*)&tmp;
    xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
    xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
    xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
    xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
    return xRes * x;
}
double sin(double x) {
    int i = 1;
    double cur = x;
    double acc = 1;
    double fact= 1;
    double pow = x;
    while (fabs(acc) > .00000001 && i < 100){
        fact *= ((2*i)*(2*i+1));
        pow *= -1 * x*x;
        acc =  pow / fact;
        cur += acc;
        i++;
    }
    return cur;
}
double cos(double x) {
    return sin(M_PI_2 - x);
}
double tan(double x) {
    return sin(x)/cos(x);
}
double sinDeg(double x) {
    return sin(x * M_PI/180);
}
double cosDeg(double x) {
    return cos(x * M_PI/180);
}
double tanDeg(double x) {
    return tan(x * M_PI/180);
}
double fceil(double x) {
    long n = (long)x;
    return n + (((x != n) && (x > 0)) ? 1 : 0);
}
double ffloor(double x) {
    long n = (long)x;
    return n + (((x != n) && (x < 0)) ? -1 : 0);
}
double fround(double x) {
    double n = ffloor(x);
    double d = x - n;
    return ((x>=0)&&(d<0.5))||((x<0)&&(d<=0.5)) ? n : n+1;
}
double fln(double x) {
    if (x>=1 && x<=2) {
        return -1.7417939 + (2.8212026 + (-1.4699568 + (0.44717955 - 0.056570851 * x) * x) * x) * x;
    } else if (x<1) {
        return -fln(1.0/x);
    }
    NSUInteger log2;
    double divisor, z, result;
    NSUInteger v = (NSUInteger)x; // 32-bit word to find the log base 2 of
    NSUInteger r = 0; // r will be lg(v)
    while (v >>= 1) { // unroll for more speed...
        r++;
    }
    log2 = r; // See: https://stackoverflow.com/a/4970859/6630230
    divisor = (double)(1 << log2);
    z = x / divisor;    // normalized value between [1.0, 2.0]
    result = -1.7417939 + (2.8212026 + (-1.4699568 + (0.44717955 - 0.056570851 * z) * z) * z) * z;
    result += ((double)log2) * 0.69314718; // ln(2) = 0.69314718
    return result;
}
double flog(double a, double x){
    return fln(x)/fln(a);
}
double flog10(double x){
    return flog(10, x);
}
double flog2(double x){
    return flog(2, x);
}
@implementation NSArray (Extension)
+(instancetype)integerArrayWithRange:(NSRange)range
{
    NSMutableArray *result = [NSMutableArray array];
    for (UInt loc = range.location; loc< range.location + range.length; loc++) {
        [result addObject: @(loc)];
    }
    return result;
}
-(NSMutableArray*)integerArray
{
    NSMutableArray *result = [NSMutableArray array];
    for (id obj in self) {
        [result addObject: @([obj integerValue])];
    }
    return result;
}
-(NSMutableArray*)stringArray
{
    NSMutableArray *result = [NSMutableArray array];
    for (id obj in self) {
        [result addObject: [obj stringValue]];
    }
    return result;
}
-(Int*)integerCArray
{
    Int N = [self count];
    Int *numbers = (Int*)malloc(N * sizeof(Int));
    for (Int i=0; i<N; i++) {
        numbers[i] = [[self objectAtIndex:i] integerValue];
    }
    return numbers;
}
-(char**)stringCArrayWithMaxLength:(UInt)maxLength
{
    Int N = [self count];
    char **matrix = (char**)malloc(N * sizeof(char*));
    char *baseMatrix = (char*)malloc(N * maxLength * sizeof(char));
    for (Int i=0; i<N; i++) {
        matrix[i] = baseMatrix + i * maxLength;
    }
    for (Int i=0; i<N; i++) {
        NSString *str = [self objectAtIndex: i];
        strcpy(baseMatrix + i * maxLength, [str UTF8String]);
    }
    return matrix;
}
-(Int)integerAtIndex:(UInt)index
{
    return [[self objectAtIndex:index] integerValue];
}
-(Int)firstInteger
{
    return [self integerAtIndex: 0];
}
-(Int)secondInteger
{
    return [self integerAtIndex: 1];
}
-(Int)thirdInteger
{
    return [self integerAtIndex: 2];
}
-(Int)fourthInteger
{
    return [self integerAtIndex: 3];
}
-(double)doubleAtIndex:(UInt)index
{
    return [[self objectAtIndex:index] doubleValue];
}
-(NSString*)stringAtIndex:(UInt)index
{
    return (NSString*)[self objectAtIndex:index];
}
-(NSMutableArray*)indexesOfObject:(id)object
{
    NSMutableArray *indexes = [NSMutableArray array];
    UInt i = 0;
    for (id obj in self) {
        if ([obj isEqual:object]) {
            [indexes push: @(i)];
        }
        i++;
    }
    return indexes;
}
-(NSArray*)subarrayTo:(UInt)index
{
    return [self subarrayWithRange: NSMakeRange(0, index+1)];
}
-(NSArray*)subarrayFrom:(UInt)index
{
    return [self subarrayWithRange: NSMakeRange(index, [self count] - index)];
}
-(NSArray*)subarrayFrom:(UInt)start to:(UInt)end
{
    return [self subarrayWithRange: NSMakeRange(start, end - start + 1)];
}
-(NSArray*)filteredArrayUsingPredicateFormat:(NSString*)format, ...
{
    va_list arguments;
    va_start(arguments, format);
    NSPredicate *predicate = [NSPredicate predicateWithFormat: format arguments: arguments];
    NSArray *result = [self filteredArrayUsingPredicate: predicate];
    va_end(arguments);
    return result;
}
-(NSMutableArray*)rotatedArrayBy:(Int)advance
{
    NSMutableArray *array = [NSMutableArray arrayWithArray: self];
    UInt n = [self count];
    advance %= n;
    if (advance>0) {
        NSIndexSet *from = [NSIndexSet indexSetWithIndexesInRange: NSMakeRange(0, advance)];
        [array moveObjectsFromIndexes: from toIndex: n];
    } else if (advance < 0) {
        NSIndexSet *from = [NSIndexSet indexSetWithIndexesInRange: NSMakeRange(n+advance, -advance)];
        [array moveObjectsFromIndexes: from toIndex: 0];
    }
    return array;
}
-(NSMutableArray*)reversedArray
{
    NSMutableArray *array = [NSMutableArray array];
    NSEnumerator *enumerator = [self reverseObjectEnumerator];
    id obj;
    while((obj = [enumerator nextObject])) {
        [array addObject: obj];
    }
    return array;
}
-(NSMutableArray*)intersectionArrayWith:(NSArray*)array
{
    NSMutableArray *result = [NSMutableArray array];
    NSMutableArray *target = [NSMutableArray arrayWithArray:array];
    for (id obj in self) {
        NSUInteger index = [target indexOfObject:obj];
        if (index != NSNotFound) {
            [result push: obj];
            [target removeObjectAtIndex:index];
        }
    }
    return result;
}
-(NSMutableArray*)sortedStringArrayWithAscending:(BOOL)ascending
{
    SEL selector = ascending ? @selector(compare:) : @selector(compareInReverseOrder:);
    return [NSMutableArray arrayWithArray: [self sortedArrayUsingSelector: selector]];
}
-(NSMutableArray*)sortedArrayWithAscending:(BOOL)ascending
{
    NSSortDescriptor *descriptor = [[[NSSortDescriptor alloc] initWithKey: @"self" ascending: ascending] autorelease];
    NSArray *sortedArray = [self sortedArrayUsingDescriptors: @[descriptor]];
    return [NSMutableArray arrayWithArray: sortedArray];
}
-(NSMutableArray*)quickSortedArrayWithAscending:(BOOL)ascending
{
    // Time complexity: O(n^2).
    //  * First time arround is to separate the entire array.
    //  * Second time around should sort the rest of the array.
    // Space complexity: O(log n)  +1 for unsortedArray but the mutable copy never gets added to the autorelease pool.
    // All of the arrays that are not attached to the returnArray are released by a compiler pass at the end of the method.
    UInt count = [self count];
    if (count <= 1) {
        return [NSMutableArray arrayWithArray: self];
    }
    Int pivot = [[self objectAtIndex: (count/2)] integerValue];
    NSMutableArray *smallerThanArray = [NSMutableArray array];
    NSMutableArray *largerThanArray = [NSMutableArray array];
    NSMutableArray *pivotArray = [NSMutableArray array];
    [pivotArray addObject: @(pivot)];
    for (Int e = 0; e < count; e++) {
        Int num = [[self objectAtIndex:e] integerValue];
        if (num < pivot) {
            [smallerThanArray addObject: @(num)];
        } else if (num > pivot) {
            [largerThanArray addObject: @(num)];
            // To address the possibly duplicate that is defined in the pivot, in this case 4.
        } else if (e != (count/2) && pivot == num) {
            [pivotArray addObject: @(num)];
        }
    }
    NSMutableArray *returnArray = [NSMutableArray array];
    if (ascending) {
        [returnArray addObjectsFromArray: [smallerThanArray quickSortedArrayWithAscending: ascending]];
        [returnArray addObjectsFromArray: pivotArray];
        [returnArray addObjectsFromArray: [largerThanArray quickSortedArrayWithAscending: ascending]];
    } else {
        [returnArray addObjectsFromArray: [largerThanArray quickSortedArrayWithAscending: ascending]];
        [returnArray addObjectsFromArray: pivotArray];
        [returnArray addObjectsFromArray: [smallerThanArray quickSortedArrayWithAscending: ascending]];
    }
    return returnArray;
}
-(NSMutableArray*)quickSortedDictionariesWithValueForKey:(id)key ascending:(BOOL)ascending
{
    UInt count = [self count];
    if (count <= 1) {
        return [NSMutableArray arrayWithArray: self];
    }
    NSDictionary *pivotDict = (NSDictionary*)[self objectAtIndex: (count/2)];
    Int pivot = [[pivotDict objectForKey: key] integerValue];
    NSMutableArray *smallerThanArray = [NSMutableArray array];
    NSMutableArray *largerThanArray = [NSMutableArray array];
    NSMutableArray *pivotArray = [NSMutableArray array];
    [pivotArray addObject: pivotDict];
    for (Int e = 0; e < count; e++) {
        NSDictionary *current = (NSDictionary*)[self objectAtIndex:e];
        Int num = [[current objectForKey: key] integerValue];
        if (num < pivot) {
            [smallerThanArray addObject: current];
        } else if (num > pivot) {
            [largerThanArray addObject: current];
        } else if (e != (count/2) && pivot == num) {
            [pivotArray addObject: current];
        }
    }
    NSMutableArray *returnArray = [NSMutableArray array];
    if (ascending) {
        [returnArray addObjectsFromArray: [smallerThanArray quickSortedDictionariesWithValueForKey: key ascending: ascending]];
        [returnArray addObjectsFromArray: pivotArray];
        [returnArray addObjectsFromArray: [largerThanArray quickSortedDictionariesWithValueForKey: key ascending: ascending]];
    } else {
        [returnArray addObjectsFromArray: [largerThanArray quickSortedDictionariesWithValueForKey: key ascending: ascending]];
        [returnArray addObjectsFromArray: pivotArray];
        [returnArray addObjectsFromArray: [smallerThanArray quickSortedDictionariesWithValueForKey: key ascending: ascending]];
    }
    return returnArray;
}
-(Int)gcd
{
    UInt count = [self count];
    switch (count) {
        case 0:
            return 0;
        case 1:
            return [[self objectAtIndex:0] integerValue];
        case 2:
        {
            Int a = [[self objectAtIndex:0] integerValue];
            Int b = [[self objectAtIndex:1] integerValue];
            return gcd(a,b);
        }
        default:
        {
            UInt c = [self count];
            NSRange range1 = NSMakeRange(0, c/2);
            NSRange range2 = NSMakeRange(c/2, count - c/2);
            NSArray *a = [self subarrayWithRange: range1];
            NSArray *b = [self subarrayWithRange: range2];
            return gcd([a gcd], [b gcd]);
        }
    }
}
/// MARK:- Key-Value Coding
-(NSMutableArray*)unique
{
    return [NSMutableArray arrayWithArray:[self valueForKeyPath:@"@distinctUnionOfObjects.self"]];
}
-(Int)maxInteger
{
    return [[self valueForKeyPath:@"@max.self"] integerValue];
}
-(Int)minInteger
{
    return [[self valueForKeyPath:@"@min.self"] integerValue];
}
-(Int)sumInteger
{
    return [[self valueForKeyPath:@"@sum.self"] integerValue];
}
-(double)maxDouble;
{
    return [[self valueForKeyPath:@"@max.self"] doubleValue];
}
-(double)minDouble;
{
    return [[self valueForKeyPath:@"@min.self"] doubleValue];
}
-(double)sumDouble;
{
    return [[self valueForKeyPath:@"@sum.self"] doubleValue];
}
-(double)average;
{
    return [[self valueForKeyPath:@"@avg.self"] doubleValue];
}
#ifndef _OS_OSTYPES_H
-(id)firstObject
{
    if ([self count] > 0) {
        return [self objectAtIndex: 0];
    } else {
        return nil;
    }
}
#endif
-(id)secondObject
{
    if ([self count] > 1) {
        return [self objectAtIndex: 1];
    } else {
        return nil;
    }
}
-(id)thirdObject
{
    if ([self count] > 2) {
        return [self objectAtIndex: 2];
    } else {
        return nil;
    }
}
-(id)fourthObject
{
    if ([self count] > 3) {
        return [self objectAtIndex: 3];
    } else {
        return nil;
    }
}
@end
int compare_int(const void *a, const void *b) {
    long A = *(long*)a;
    long B = *(long*)b;
    return (B>A) ? 1 : (B==A) ? 0 : -1 ;
}
void inc(NSMutableDictionary *dic, long val, long inc) {
    NSNumber *obj = [dic objectForKey:@(val)];
    if(obj) {
        [dic setObject:@([obj longValue]+inc) forKey:@(val)];
    }else {
        [dic setObject:@(inc) forKey:@(val)];
    }
}
int main(){
    @autoreleasepool {
        long N,M;
        scanf("%ld %ld",&N,&M);
        NSMutableDictionary *dic = [NSMutableDictionary dictionary];
        NSMutableSet *set = [NSMutableSet set];
        long min = LONG_MAX;
        for(long i=0;i<N;i++){
            long a;
            scanf("%ld",&a);
            min = MIN(min,a);
            [set addObject:@(a)];
            inc(dic, a, 1);
        }
        for(long i=0;i<M;i++){
            long b,c;
            scanf("%ld %ld",&b,&c);
            if(c<=min){
                continue;
            }
            inc(dic, c, b);
            [set addObject:@(c)];
        }
        long *ary = [[set allObjects] integerCArray];
        qsort(ary, [set count], sizeof(long), compare_int);
        long sum=0;
        long i=0;
        while(N>0){
            long val = ary[i];
            long count = [[dic objectForKey:@(val)] longValue];
            if(N >= count) {
                sum += val*count;
                N -= count;
            }else{
                sum += val*N;
                N = 0;
            }
            i++;
        }
        printf("%ld",sum);
    }
}


Measured memory_bytes: 52640