"""
출처:프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/60062
"""

# 풀이 과정
"""
1시간 
보내야 할 친구 수

n:외벽 길이
weak:취약 지점
dist:친구들이 이동 할 수 있는 길이

시간 초과 발생 > 중복을 제거할 알고리즘 및 아이디어 구현 생각해보기 

"""
from itertools import permutations


def solution(n, weak, dist):
    # waek 개수
    weak_point = len(weak)

    # 최대 사람 수 +1 > 최대 사람으로도 부족할 시 > -1
    person = len(dist) + 1

    # 원형을 펴서 직선으로 만들기 > 시계 방향, 반시계 방향으로 두 가지를 동시에 하기 위해서
    line = weak

    for i in range(weak_point):
        line.append(weak[i] + n)

    # 사람 배치 순서
    person_rotation = list(permutations(dist, len(dist)))

    for start in range(weak_point):
        for p in person_rotation:

            # 사람 수(취약점이 없을 수도 있다)
            cnt = 0
            # 0명일때는 취약점 조사 불가 > -1로 표현함으로써 취약점 조사 불가 표현
            location = -1

            # weak 포인트 개수가 동일하게 하기 위해 start+weak_point
            for i in range(start, start + weak_point):
                if location < line[i]:
                    cnt += 1
                    # 사람 수 len(dist)
                    if cnt > len(dist):
                        break

                    # 거리 낭비를 최소화 > 취약점에서 시작
                    location = line[i] + p[cnt - 1]

            person = min(person, cnt)

    if person > len(dist):
        return -1

    return person