New Album

Time limit2sMemory limit128 MB

Summary

Given song length, CD capacity, and a superstition banning CD track counts divisible by 13, find the minimum number of CDs needed to fit all songs.

Level: Medium5 of 10
Topics: Greedy, Math, Simulation
Solved: No attempts yet

Problem

A band is preparing a new album with N songs of equal length. Each song is L seconds long, and one CD can store at most C seconds of audio.

If two or more songs are placed on the same CD, there must be a 1-second pause between each pair of consecutive songs. Therefore, putting x songs on one CD requires x * L + (x - 1) seconds.

Because of a superstition, no CD may contain a number of songs that is divisible by 13. Determine the minimum number of CDs needed to include all N songs.

Input

The first line contains the number of songs N. N is a natural number no greater than 100,000.

The second line contains the length L of each song in seconds.

The third line contains the capacity C of one CD in seconds. C is a natural number no greater than 10,000, and L is a natural number no greater than C.

Output

Print the minimum number of CDs needed to store all songs.

Hint

In the first public test, at most two songs can fit on one CD.

Examples6

Example 1
Input
```
7
2
6
```
Expected output
```
4
```
Example 2
Input
```
20
1
100
```
Expected output
```
1
```
Example 3
Input
```
26
1
100
```
Expected output
```
2
```
Example 4
Input
```
26
3
51
```
Expected output
```
3
```
Example 5
Input
```
67
271
1000
```
Expected output
```
23
```
Example 6
Input
```
27
1
27
```
Expected output
```
3
```