Given an array of size N$N$ and two integers K$K$ and S$S$, the special sum of a subarray is defined as follows:

(Sum of all elements of the subarray) * (K$K$ - p$p$ * S$S$)

Where p$p$ = number of distinct prime factors of “product of all elements of the subarray”.

Find the maximum special sum by considering all non-empty subarrays of the given array.

-----Input-----
- First line contains 3 integers N$N$, K$K$ and S$S$.     
- Second line contains N$N$ integers, the elements of the array.  

-----Output-----
Output a single integer. The maximum special sum considering all non-empty subarrays of the array.

-----Constraints:-----
- 1≤N,K,S≤105$ 1 \leq N, K, S \leq 10^5 $ 
- 0≤K/S≤20$ 0 \leq K / S \leq 20 $ 
- 1<$ 1 < $ Any element of array <105$ < 10^5 $

-----Sample Input-----
4 10 2

14 2 7 15

-----Sample Output-----
138

-----Sample Explanation-----
Consider the subarray {14, 2, 7}

Total number of distinct prime factors in it is 2 (2 and 7).

Therefore, value of special sum is (14 + 2 + 7) * (10 - 2 * 2) = 138.

This is the subarray with the maximum special sum.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))

from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))

# cook your dish here
from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))

from math import floor, sqrt
try:int
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),int(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = list(map(int,input().split()))
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))


from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))

from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))

# cook your dish here
from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))

from math import floor, sqrt
try:long
except NameError:long = int 
def fac(n):
    step,maxq,d = lambda x: 1 + (x<<2) - ((x>>1)<<1),long(floor(sqrt(n))),1
    q = n % 2 == 0 and 2 or 3 
    while q <= maxq and n % q != 0:
     q = step(d)
     d += 1
    return q <= maxq and [q] + fac(n//q) or [n]
n,k,s = map(int,input().split())
a,di,l,m,ans,su =list(map(int,input().split())),{},[],0,0,0
for i in a:
    bb,su = list(set(fac(i))),su+i
    for j in bb:
     try:di[j]+=1
     except KeyError:m,di[j] = m+1,1
    l.append(su*(k-m*s))
    if su*(k-m*s) <0:m,di,su = 0,{},0
print(max(l))