물탱크

시간 제한2초메모리 제한512 MB

요약

다단계 유입이 진행되는 동안 물탱크가 용량 C를 넘지 않도록 하는 최소한의 배출 속도 R을 구한다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 누적 합, 수학
정답자: 아직 제출이 없습니다

문제

용량이 $C$ 리터인 물탱크가 비어 있다. 시간 0에 파이프로 물이 들어오기 시작한다. 유입은 $n$ 개의 연속된 구간으로 나뉘고, 구간에는 0번부터 $n-1$ 번까지 번호가 붙는다. 구간 $i$ 는 $t[i]$ 초 동안 이어지며, 그동안 탱크에 1초에 $x[i]$ 리터씩 물이 들어온다.

탱크에는 배출구가 하나 있고 밸브가 달려 있다. 밸브는 1초에 $R$ 리터를 내보내며, $R$ 는 0 이상의 실수다. $R$ 는 물이 들어오기 전에 정해야 하고 유입이 끝날 때까지 바꿀 수 없다. 탱크가 비어 있는 동안에는 물이 빠져나가지 않으므로 저수량은 0 아래로 내려가지 않는다.

어느 순간에도 저수량이 $C$ 리터를 넘지 않는 가장 작은 $R$ 를 구하라.

입력

첫째 줄에 $n$ 과 $C$ 가 주어진다. ( $1 \le n \le 50$ , $1 \le C \le 10^9$ )

둘째 줄에 $t[0], t[1], \dots, t[n-1]$ 이, 셋째 줄에 $x[0], x[1], \dots, x[n-1]$ 이 주어진다. ( $1 \le t[i], x[i] \le 10^6$ )

출력

첫째 줄에 가장 작은 $R$ 를 기약분수 $p/q$ 꼴로 출력한다. $p$ 와 $q$ 는 정수이고, $q \ge 1$ 이며 $\gcd(p, q) = 1$ 이다. 답이 정수이거나 0이어도 분모를 생략하지 않는다. 답이 0이면 0/1, 답이 2이면 2/1로 출력한다.

예제4

예제 1
입력
```
2 3
3 3
1 2
```
예상 출력
```
1/1
```
예제 2
입력
```
5 10
1 2 3 4 5
5 4 3 2 1
```
예상 출력
```
2/1
```
예제 3
입력
```
1 12345
100
1000
```
예상 출력
```
17531/20
```

예제 4

입력

10 1000000000
5949 3198 376 3592 4019 3481 5609 3840 6092 4059
29 38 96 84 10 2 39 27 76 94

예상 출력

0/1