---
# System prepended metadata

title: 'Workshop 3: Greedy Solutions'

---

Workshop 3: Greedy Solutions
===

### Puzzles

```python=
n, m = map(int, input().split())
pieces = map(int, input().split())


def solve(n, m, p):
    p = sorted(p)

    i = n-1
    j = 0
    dif = 1001
    while i < m:
        dif = min(dif, p[i]-p[j])
        i += 1
        j += 1
    return dif


print(solve(n, m, pieces))

```

### Dancers

```python=

n, wc, bc = map(int, input().split())
ds = input().split()


low_cost = min(wc, bc)
cost = 0

for i, d in enumerate(ds):
    dc = ds[n - i - 1]
    if d == '2':
        if dc == '0': cost += wc
        elif dc == '1': cost += bc
        else: cost += low_cost
    elif dc != '2' and d != dc:
        cost = -1
        break

print(cost)
```

### Garbage

```python=
n, k = map(int, input().split())
a = [int(x) for x in input().split()]

bags, r = 0, 0

for i in range(n):
    x = a[i] + r
    if x == 0:
        continue
    elif x < k and r > 0:
        bags += 1
        r = 0
    else:
        bags += (x // k)
        r = (x % k)

if r > 0:
    bags += 1

print(bags)
```

### Minimum Sum

```python=
from collections import defaultdict

n = int(input())

is_first = []
d = defaultdict(int)
ans = 0

for _ in range(n):
    s = input()
    slen = len(s)
    for i in range(slen):
        t = s[i]
        if i == 0:
            if t not in is_first:
                is_first.append(t)
        num = 10 ** (slen - i - 1)
        d[t] += num


l = sorted(d.items(), key=lambda v: v[1], reverse=True)

for i, x in enumerate(l):
    if x[0] not in is_first:
        l.pop(i)
        break

for i, x in enumerate(l):
    ans += x[1] * (i+1)

print(ans)
```