Nisshinkan Marathon Club

Time Limit : 1 sec, Memory Limit : 65536 KB

ニッシン館マラソン部

アイヅ市立ニッシン館は、文武両道を掲げる歴史ある学校です。ニッシン館マラソン部は熱血指導で有名であり、決められた練習時間の間、周回コースをひたすら走るという鬼の特訓を行います。このとき、脱水症状で倒れる部員がいないように、部員の実力に合わせて飲み物を提供する給水所を設けています。

各部員が1単位時間あたりに走れる距離(ペース)は部員ごとに決まっており、全員が1単位時間ごとに必ず給水できるように給水所を設けたうえで特訓を行います。部員は 1 単位時間で着いた給水所で必ず中身の入った容器を取り、そのまま走り続けます。さらに、次の1単位時間で着いた給水所で空の容器を置き、中身の入った容器を取って走り続けるということを繰り返します。また、空の容器は、置いてから 1 単位時間の時点で飲料が補充され、その瞬間から誰にでも提供できるようになります。

部員は全員同じ地点から、容器を持たずに出発します。決められた練習時間まで走ると練習を終えます(このときも給水が必要です)。複数の部員が同時に同じ給水所に到着する場合もあるので、一か所の給水所で同時に複数の容器が必要になることもあります。

鬼の特訓を安全に行うために、最低いくつの給水容器が必要になるか求めるプログラムを作成してください。

入力

入力は以下の形式で与えられる。

N R T
p1
p2
:
pN

1行目に部員の数 N (1 ≤ N ≤ 100)、周回コースの長さ R (1 ≤ R ≤ 1000)、決められた練習時間 T (1 ≤ T ≤ 1000) が与えられる。続く N 行に、部員 i のペース pi (1 ≤ pi ≤ 1000) が与えられる。

出力

最低いくつの給水容器が必要になるかを1行に出力する。

入出力例

入力例1

1 10 20
1

出力例1

11

入力例2

2 5 12
1
2

出力例2

8

Source: PC Koshien 2014 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2014-11-8
http://web-ext.u-aizu.ac.jp/pc-concours/